Better Students Ask More Questions.
Graph Theory Question I need help with the following proof Let G Be a graph in which...
Graph Theory Question
I need help with the following proof
Let G Be a graph in which every vertext has degree
atleast 2. Prove that G contains a cycle (Hint Imagine
walking along hte graph, will you ever get ato a dead vertex,
if not, what must evedntually happen.
1 Answer | add yours
High School Teacher
Begin at vertex A. There are at least two paths to choose from; choose one at random. This process continues (you never get to a dead end because there are no vertices of degree 1) until you have either (i) visited all vertices in the graph or (ii) traversed a cycle. In case (i), the next path you choose will result in a cycle, so your graph must contain a cycle. QED!
Posted by nathanshields on January 20, 2012 at 7:29 AM (Answer #1)
Join to answer this question
Join a community of thousands of dedicated teachers and students.