Homework Help

# I need help witha  graph theory questionLet T be a tree with more than one vertex....

Student

Honors

• Up
• 0
• Down

I need help witha  graph theory question

Let T be a tree with more than one vertex. Prove that
T must have atleast two verticies of degree 1.

Posted by ashifs on November 9, 2011 at 2:32 AM via web and tagged with graph theory, math

High School Teacher

(Level 1) Associate Educator

• Up
• 0
• Down

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)