Question

Let G be a simple connected graph on 5 vertices all of degree at least 3. Must G have a Hamiltonian circuit? Explain.

Answer 1

Start by assuming each vertex has a degree of exactly 3. For any given vertex, you have \(\dbinom43=4\) possible ways of connecting to three other vertices. Here's one such arrangement:

Answer 2

Let's consider the extreme case, in which we connect one of the currently 1-degree vertices to two others. We have \(\dbinom32=3\) ways of doing so. Here's one: