Results 1 to 3 of 3

Math Help - Trees question

  1. #1
    Junior Member
    Joined
    Dec 2006
    Posts
    28

    Trees question

    Ok, I have 2 questions.

    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!
    Last edited by faure72; December 18th 2006 at 09:46 AM. Reason: wanted to make the question more clear
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2005
    Posts
    39
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2005
    Posts
    39
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How Many Trees?
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: September 12th 2010, 10:52 PM
  2. Object oriented and trees question
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: May 4th 2010, 03:43 AM
  3. Graph Theory question about trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 27th 2009, 03:52 AM
  4. how can you plant 10 trees in 5 rows of 4 trees each?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 22nd 2008, 12:43 PM
  5. Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 6th 2008, 09:24 PM

Search Tags


/mathhelpforum @mathhelpforum