1) So the center of a tree is defined as the set of vertices that have the smallest eccentricity (meaning the number of edges in a longest path that begins at a vertex x). How do you prove by induction that every tree has a center that consists of either one or two vertices?
2) Also I was wondering if T is a tree that has more than one edge, how do you prove that the center of T equals the center of p(T)? p(T) is defined as the tree that has all its leaves (leaves are vertices of degree 1) taken out (as well as the edges attached to those degree 1 vertices).
Thanx to anyone who can help!
January 6th 2007, 07:56 AM
I am actually studying trees at the moment, and have been working on a slight variant of your problem, so I'll give it a shot. In what follows, denote by d(A,B) the distance (length of the path) from a vertex A to a vertex B.
Oddly, it seems the way do to this would be to prove 2) in order to prove 1). Proving 2) would go as follows: if A is any vertex on P(T), Let B be the vertex on P(T) such that a longest path in P(T) starting at A ends at B (so that A has eccentricity d(A,B)). We know that B is a leaf on P(T), for if it were not, we could just keep going and get a longer path from A. And since B is a leaf on P(T), T is gotten from P(T) by adjoing some number of new leaves to B (as well as possibly some other leaves on other vertices). Take any new leaf C connected to B, and we have that, in T, d(A,C) = d(A,B) + 1. We claim that d(A,C) is now the eccentricity of A in T. This is because, as we just argued, the distance from A to any other new leaf is simply the distance to that leaf's "branch" plus 1.
Thus, we've shown that the eccentricity of a vertex A inside T is equal to the eccentricity of A inside P(T), plus 1. So if the eccentricity of A inside P(T) is smaller than B's inside P(T), it must also be inside T as well.
We have to finally argue that none of the new leaves on T can qualify as centers for T. Let L be a leaf on T, and let B be the vertex (branch) that it is connected to. Then the eccentricity of L is equal to the eccentricity of B plus 1, so L immediately has greater eccentricity than another vertex in T. Thus L is not a center of T.
Thus we have proved 2).
Now, how to prove 1). I have not gone through this yet, but I'm pretty sure it can be proved using an induction argument. The trick is to realize that, starting with a tree T, and going to P(T), and then to P(P(T)), etc, you will eventually end up with a tree having exactly one or two vertices. The theorem is obviously true for such trees. And from part 2), we know that the center of T = center of P(T) = center of P(P(T)) = ... = center of the tree we finally end up with, which consists of 1 or 2 vertices.
Hope that was clear, let me know if any of it was not.
January 6th 2007, 08:00 AM
By the way, I'm glad you posted this, part 2) I think will be a big hint for me in solving a similar problem (the problem I'm working on defines the "eccentricity" of A to be the sum of all the distances to all other vertices in T, and the center again to be the vertex with the smallest eccentricity).