Homework Help

I need help with a graph theory questionb) Let T be a tree with more then one vertex,...

user profile pic

ashifs | Student, Undergraduate | Honors

Posted November 9, 2011 at 2:31 AM via web

dislike 0 like

I need help with a graph theory question

b) Let T be a tree with more then one vertex, prove that T must
have atleast one vertex of degree 1


Tagged with graph theory, math

1 Answer | Add Yours

user profile pic

embizze | High School Teacher | (Level 1) Educator Emeritus

Posted November 10, 2011 at 11:54 AM (Answer #1)

dislike 0 like

A tree is an acyclic, connected graph. If the graph has more than one vertex, and every vertex has at least degree two, then there must be a cycle which contradicts the given that the graph is a tree.

Any vertex of degree at least 2 is a cut vertex, and any nontrivial graph contains at least two vertices that are not cut vertices.

Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes