Graph Theory – Showing that No Hamilton Circuit Exists

discrete mathematicsgraph theory

I was confused about a certain concept and I was wondering if I could get some help.

There were three points that were made in my textbook to show that a graph does not contain a Hamilton circuit:

  1. A graph with a vertex of degree one cannot have a Hamilton circuit.
  2. Moreover, if a vertex in the graph has degree two, then both edges that are incident with this vertex must be part of any Hamilton circuit.
  3. A Hamilton circuit cannot contain a smaller circuit within it.

I understand 1 and 3, but I'm a bit confused about 2. I wasn't really sure how this helps. I realize that the definition of a Hamilton circuit is a simple circuit in a graph that traverses over all vertices in the graph. But this is exactly what we are trying to disprove, so how is it helpful to say that both edges must be part of a Hamilton circuit when we don't even know if the graph contains a Hamilton circuit? How is that not circular?

Hopefully you can understand my confused, sleep deprived thought process. If you can't, could somebody at least elaborate on the significance of number 2?

Thanks for the help.

Best Answer

Suppose that $v$ is a vertex of degree $2$. If $G$ has a Hamilton circuit, that circuit must pass through $v$, so it must include both of the edges incident at $v$. In particular, if the configuration

              o----o----o  
              u    v    w

occurs anywhere in $G$, it must be part of any Hamilton circuit in $G$. Such a circuit must be a circuit, so it must include some other path from $u$ to $w$ as well. This can be useful in proving that a graph does not have a Hamilton circuit: if there is no other path between $u$ and $w$ in $G$, then $G$ cannot have a Hamilton circuit.

Related Question