Show that a finite graph with all vertices with degree $\geq 2$ has a cycle that contains a vertex which is non-adjacent to any other vertices not contained in the cycle.

I know how to prove that the graph has at least a cycle: just start somewhere and follow the path. If you ever have an option to go back to a vertex you have visited, you have found a cycle. You can never get stuck as each vertex you come to has an exit. Eventually you will run out of vertices.

However, how would i find this special cycle? i tried contradiction, suppose the cycle does not have any such vertex. Then all vertices in the cycle must connect to at least one other vertex not in the cycle. how would i find a contradiction?

  • 1
    $\begingroup$ Try enlarging the cycle you have found. If you can always do it, then there is no longest cycle in the graph, contradiction. $\endgroup$ – saulspatz Apr 26 at 12:10
  • $\begingroup$ do you assume your graph is finite? otherwise an infinite line or tree is a counterexample. $\endgroup$ – Rylee Lyman Apr 26 at 12:16
  • $\begingroup$ yes its finite and why is no longest cycle a contradiction? $\endgroup$ – james black Apr 26 at 12:16
  • $\begingroup$ and if its a finite graph how can i always do it? $\endgroup$ – james black Apr 26 at 12:22
  • $\begingroup$ Start at an arbitrary $v \in V$ and let $P$ be a maximal path beginning at $v$. Let $u$ be the endpoint of $P$. Then, all neighbors of $u$ must be in $P$ (why?). Can you go on from here? $\endgroup$ – Nicolas Apr 26 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.