- Thread starter
- #1

The edges in red are the paths that must be included in the cycle, since vertices

a, k, e, and o have only degree 2.

I listed all possible routes starting from vertex b, and showed that they all routes closes a cycle while leaving some vertex disconnected.

Is there a more efficient way?

In general, when asked to show that a graph doesn't contain something, what is the usual procedure for proving it?