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...

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.


Asked on by ashifs

1 Answer | Add Yours

nathanshields's profile pic

nathanshields | High School Teacher | (Level 1) Associate Educator

Posted on

Proof

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!

We’ve answered 333,965 questions. We can answer yours, too.

Ask a question