Results 1 to 2 of 2

Math Help - Trees

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Trees

    Let T be a tree with n >= 2 vertices and let v e V(T). Prove that if T - v is a tree, then v is a leaf.

    How does one go about solving this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by jzellt View Post
    Let T be a tree with n >= 2 vertices and let v e V(T). Prove that if T - v is a tree, then v is a leaf.

    How does one go about solving this?
    My suggestion would be to find a theorem in your book that says something along the lines of "a tree is defined as a connected graph where there is a unique simple path between any two vertices" then point out that if the graph is unique, then there are no circuits, so breaking that path (removing any vertice along the path) would cause the tree to become unconnected. Thus it is not a tree. So if you remove a node, and the tree is still a tree, then that node cannot be along the path between any two nodes, thus it must have only one edge associated with it, and therefore must be a leaf.

    You'll want to find the theorems that define a tree as I have defined it, and that define a leaf as a node with only one edge, and then reword it to be more rigorous.
    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, 09:52 PM
  2. Trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 21st 2009, 12:00 PM
  3. 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, 11:43 AM
  4. trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 22nd 2007, 09:22 AM
  5. Help with trees
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: October 29th 2006, 10:22 AM

Search Tags


/mathhelpforum @mathhelpforum