I'm finding distance and diameter confusing in graph theory. Distance is the smallest path between two vertices. Diameter is the largest smallest path? Is it possible for a connected graph to have a diameter greater than the largest distance between any two vertices?
[Math] Distance vs diameter in graph theory
graph theory
Related Solutions
As for 1), it seems you got the right idea but what does "Every two vertices include adjacent ones as well." mean ?
My personal way of saying it would be : if you have two vertices $u, v$ at distance 3 or 5, then necessarily there's a vertex at distance 2 from $u$ on the shortest $u - v$ path (That's what point 2. says !). So the only available odd distance is actually 1, which leaves only one possibility.
For 2), you might want to complete the proof by stating why you can't have $d(u, v_i) < i$, nor $d(u, v_i) > i$ for any $1 \leq i < k$. That is, $d(u, v_k) = k$ by definition, but what about the other values of $i$.
From the comments it looks like you got a bit confused for the definitions of diameter and distance.
The diameter is not the maximum path length between any two vertices. The diameter of the graph is the maximum distance between any two vertices. And the distance between two vertices is the length of the shortest path.
Given the shortest path $ABCF$, the distance between $A$ and $F$ is 3, and this is fixed. Even if there exist longer paths such as $ADEBCF$, the distance is still 3. We can reach $F$ from $A$ in 3 steps. Therefore the eccentricity of $A$ is $3$, not $5$.
The diameter is a max/min value. If $V$ is our set $\{A,B,C,D,E,F\}$ $$ diam = \max_{x,y\in V} \{distance(x,y)\}$$ $$ diam = \max_{x,y\in V} \{\min_{path(x\to y) }length(path)\}$$
The distance between $A$ and $F$ is fixed at 3, so we know that $diam\geq 3$. In order to find the diameter of the graph, you need to check the distance between all other pairs of vertices. It is easy to see that for any other pair of vertices the distance is less than 3. Therefore $$diam = 3$$
Regarding the last question : when you remove a vertex, you remove all the edges that "end" at this vertex (we say all edges incident with this vertex). For example if you remove the vertex $A$, you get the following subgraph.
I'm sure you can finish from here.
Best Answer
"largest distance between any two vertices" is an alternative definition for diameter.
At least when the graph is connected, but talking about diameter in unconnected graphs is not common.