Math Help Forum

Math Help Forum Feed Site Feed

Go Back   Math Help Forum > University Math Help > Discrete Mathematics, Set Theory and Logic
Reply
 
Thread Tools Display Modes
  #1  
Old May 6th, 2008, 05:09 PM
Senior Member
 
Join Date: Feb 2008
Posts: 272
Country:
Thanks: 77
Thanked 0 Times in 0 Posts
jzellt is on a distinguished road
Default 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?
Reply With Quote
Advertisement
 
  #2  
Old May 6th, 2008, 09:24 PM
angel.white's Avatar
Super Member
 
Join Date: Oct 2007
Posts: 723
Country:
Thanks: 250
Thanked 241 Times in 195 Posts
angel.white is a jewel in the roughangel.white is a jewel in the roughangel.white is a jewel in the rough
Default

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.
__________________
two can keep a secret if one of them is dead
Reply With Quote
The following users thank angel.white for this useful post:
Donate to MHF
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are Off
Pingbacks are Off
Refbacks are Off
Forum Jump


All times are GMT -7. The time now is 03:43 AM.


Powered by vBulletin® Version 3.7.3
Copyright ©2000 - 2010, Jelsoft Enterprises Ltd.
SEO by vBSEO 3.2.0 ©2008, Crawlability, Inc.
©2005 - 2009 Math Help Forum


Math Help Forum is a community of maths forums with an emphasis on maths help in all levels of mathematics.
Register to post your math questions or just hang out and try some of our math games or visit the arcade.