Results 1 to 2 of 2

Math Help - Proof Involving Trees and Leafs

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    42

    Proof Involving Trees and Leafs

    Prove:

    Let T be a tree with at least two vertices and let v be an element of V(T). If v is not a leaf, then T - v is not a tree.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by dynas7y View Post
    Prove:

    Let T be a tree with at least two vertices and let v be an element of V(T). If v is not a leaf, then T - v is not a tree.
    Consider the following definition of the tree:
    "Any two vertices in T can be connected by a unique simple path."

    Since v is not a leaf node and T has at least two vertices, v must have at least two nodes connected to it. Call them x and z. Clearly by the definition of a tree, the path between x and z is only via v.
    If T - v is a tree, then there still exists a unique simple path between x and z when v has been removed. This contradicts the fact that the path between x and z is only via v.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof involving GCD
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: October 11th 2010, 04:15 PM
  2. Trees and their complements, proof by induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 12th 2010, 12:06 PM
  3. Proof involving GCD
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: December 5th 2009, 05:36 PM
  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. [SOLVED] Binary tree - number of leafs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 3rd 2008, 09:11 AM

Search Tags


/mathhelpforum @mathhelpforum