Better Students Ask More Questions.
I need help witha graph theory questionLet T be a tree with more than one vertex....
1 Answer | add yours
High School Teacher
Proof by induction.
I. Initial condition. Let T be a tree with 2 vertices. Then T has two vertices of degree 1, by definition of tree (connected graph without cycles).
II: Rule of induction. Let b U be a tree with n, and addume that U has at least 2 vertices of degree 1. Adding another vertex will either (i) maintain the number of vertices of degree 1 (by connecting to a vertex of degree one) or (ii) increase the number of vertices of degree 1 (by connecting to a vertex of degree greater than 1).
Taking I and II together means that any tree with 2 or more vertices will contain at least two vertices of degree 1. QED
Posted by nathanshields on January 20, 2012 at 7:25 AM (Answer #1)
Join to answer this question
Join a community of thousands of dedicated teachers and students.