graph theorytrees
I want to find center in a graph that doesn't have cycles. I heard, that this is how I find a diameter:
And then I just divide it equally.
But how to prove this diameter finding algorithm? Why is it valid?
The distance is defined as the number of edges on the shortest path between the vertices. For example, adjacent vertices have a distance of $1$.
In your graph, it might be helpful to explicitly enumerate the eccentricity of each vertex. It is not too difficult to eye-ball the eccentricity for each vertex. I have labelled your graph below with the vertex eccentricities
You can see that in this graph, the larger eccentricities occur at the sides of the graph, with the largest (the diameter) being $6$. The smallest eccentricity occurs at the central vertex with an eccentricity of $3$. This is your radius. Your center consists of all the vertices which have eccentricity equal to the radius, in this case $3$. For this graph, there is only a single such vertex, so your center in the single vertex labelled $3$ in the graph.
You can see that the name center really is quite aptly named. The vertices of the center minimizes the maximum distance to any vertex of the graph and in this sense, really are the most central vertices in the graph.
The proof is fine, provided that you restore the two observations whose necessity you’re questioning.
The observation that the eccentricity of a vertex $v$ in $T'$ is one less than the eccentricity of $v$ in $T$ (in symbols: $\epsilon_{T'}(v)=\epsilon_T(v)-1$) is needed in order to show that the vertices of minimal eccentricity in $T'$ are the same as those in $T$: we need to know that $\epsilon_T(u)<\epsilon_T(v)$ if and only if $\epsilon_{T'}(u)<\epsilon_{T'}(v)$, so that the ordering of vertices by increasing eccentricity doesn’t change when we go from $T$ to $T'$.
The observation that any vertex at maximal distance from some vertex $v$ of $T$ is a leaf is needed to prove the previous observation. Removing the leaves of $T$ removes the vertices at maximum distance from a given interior vertex $v$, thereby reducing the eccentricity of $v$ by at least $1$. It does not, however, remove the neighbors of those vertices, which are at distance $\epsilon_T(v)-1$ from $v$, so it reduces the eccentricity only by $1$.
Best Answer
The solution for problem 4 in HW3_Solution.pdf gives a detailed proof. There is also the same question Prove traversing a k-ary tree twice yields the diameter asked on Stack Overflow.