why is the Petersen Graph the smallest hypohamiltonian graph?

Question

I know that the Petersen graph is hypohamiltonian. (Which means it is not hamiltonian, but each vertex-deleted subgraph is.)

Why is it the smallest hypohamiltonian graph?

(without considering $K_2$ )

Answer 1

Lemma 1. If $G$ is a hypohamiltonian graph, $\delta(G)\geq 3$.

Proof. Consider any vertex $v \in V(G)$, and let $vw \in E(G)$. Then $G \backslash w$ is hamiltonian, and so $v$ has degree at least 2 in $G \backslash w$, and thus degree at least 3 in $G$. $\Box$

Lemma 2. If $G$ is a hypohamiltonian graph, $\Delta(G) \leq \left \lfloor \frac{n-1}{2} \right \rfloor$.

Proof. Let $v \in V(G)$ with $d_G(v) > \frac{n-1}{2}$, then $G \backslash v$ has a Hamiltonian cycle $C$, but since $d_G(v) > \frac{n-1}{2}$, $v$ is adjacent to two consecutive vertices of $C$, and $G$ itself is Hamiltonian. $\Box$

Theorem. If $G$ is hypohamiltonian, then $|V(G)| \geq 10$.

Proof. Lemmas 1 and 2 imply $|V(G)| \geq 7$ for any hypohamiltonian graph $G$. If $|V(G)|=7$, then by Lemmas 1 and 2, $G$ is cubic, but there is no odd-order cubic graph.

Suppose $|V(G)| = 8$, and $V(G) = \{v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8\}$. Lemmas 1 and 2 imply $G$ is cubic. Now $G \backslash v_8$ is hamiltonian, so we may assume $C = v_1 v_2 v_3 v_4 v_5 v_6 v_7 v_1$ is a cycle in $G$. Since $G$ is non-hamiltonian, $v_8$ is not adjacent to two consecutive vertices of $C$, but $d_G(v_8) = 3$, so we may assume WLOG $v_1 v_8, v_3 v_8, v_5 v_8 \in V(G)$. Finally, since $G$ is cubic, there are only two possibilities for the remaining edges: either $v_2 v_6, v_4 v_7 \in E(G)$, or $v_2 v_7, v_4 v_6 \in E(G)$. Both give rise to hamiltonian graphs, shown below.

                                             

Suppose $|V(G)| = 9$, and $V(G) = \{v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8,v_9\}$. Lemmas 1 and 2 imply all vertices of $G$ have either degree 3 or 4. Since $G$ has an odd number of vertices, there must be at least one vertex of degree 4. Assume $d_G(v_9) = 4$. Again, we may assume $C = v_1 v_2 v_3 v_4 v_5 v_6 v_7 v_8 v_1$ is a cycle in $G$, and that $v_9$ is not adjacent to two consecutive vertices of $C$. So we may assume $v_1 v_9$, $v_3 v_9$, $v_5 v_9$, and $v_7 v_9 \in E(G)$. Now if one of $v_2$, $v_4$, $v_6$, or $v_8$ is adjacent in $G$ to any other of those vertices, one of the following is a subgraph of $G$, and thus $G$ is Hamiltonian:

                                             

So $v_2$, $v_4$, $v_6$, or $v_8$ can only be adjacent to $v_1$, $v_3$, $v_5$, and $v_7$, and since all vertices in $G$ have degree at most 4, we can show $G$ is isomorphic to the first graph shown below. This graph is non-Hamiltonian, but deleting the red vertex of that graph gives the second graph shown, and the edges incident with vertices of degree 2 in this graph form $C_6$, so it is also non-Hamiltonian. $\Box$

                                             

Since the Petersen graph is a hypohamiltonian cubic graph on 10 vertices, it is a smallest hypohamiltonian graph. Proving it is the unique smallest hypohamiltonian graph might take a bit more work.