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.

Expert Answers

An illustration of the letter 'A' in a speech bubbles

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

See eNotes Ad-Free

Start your 48-hour free trial to get access to more than 30,000 additional guides and more than 350,000 Homework Help questions answered by our experts.

Get 48 Hours Free Access
Approved by eNotes Editorial