I am preparing to take my first course in graph theory. I have a very limited amount of experience with graph theory proofs from a previous course in mathematical proofs.
My textbook gives (essentially) the following proof but it includes some additional statements that I don't think are necessary.
Proof by induction on n, the number of vertices in a tree T.
Basis step: If n= 1 or 2 then the center is the entire tree which is a vertex or an edge.
Induction hypothesis. Let n>2. Let T be a tree with n vertices. Assume the center of every tree with less than n vertices is a vertex or an edge. Form T' by deleting the leaves of T. Since the internal vertices on paths between leaves remain, T' has at least one vertex. The eccentricity of a leaf in T is greater than that of its neighbor. Hence the vertices of minimal eccentricity in T are the same as the vertices of minimal eccentricity in T'. This implies that the center of T' is the same as the center of T. By induction hypothesis the center of T' is a vertex or an edge.
Is the above proof valid?
The textbook proof included the statement that the eccentricity of every vertex in T' is one less than in T. It also stated that every vertex at maximal distance from any vertex in T is a leaf.
I understand the validity of these two statements but I do not know why they are necessary for the proof.
Best Answer
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$.