I need help with a graph theory questionb) Let T be a tree with more then one vertex, prove that T musthave atleast one vertex of degree 1 

Asked on by ashifs

1 Answer | Add Yours

embizze's profile pic

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

Posted on

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.

We’ve answered 320,008 questions. We can answer yours, too.

Ask a question