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

Question

anonymous · Answer

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:
|dw:1430965672570:dw|

anonymous · Answer

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:
|dw:1430965854041:dw|