$3$-connected non-hamiltonian graph with at most $3$ independent vertices

Question

• Is there a $3$-connected non-hamiltonian graph with at most $3$ independent vertices ?

  I checked the graphs upto $9$ vertices and the cubic graphs upto $18$ vertices and did not find such a graph.

• If the answer is yes, which graph is the smallest ?

Answer 1

Here is the theorem that manuellafond pointed to. Here, $\kappa (G)$ is the connectivity of $G$ and $\alpha(G)$ is the independence number.

Theorem (Chvatal-Erdos): If $G$ has at least three vertices and if $\kappa (G)\geq \alpha(G)$, then $G$ is Hamiltonian.

Proof: Let $C=(v_1,v_2,\ldots,v_k)$ be a cycle of maximum length in $G$ where $v_i$ is adjacent to $v_{i+1}$ (indices taken modulo $k$). Suppose $k<|V(G)|$ and let $x\in V(G)\setminus C$. By Menger's Theorem (See Diestel's book 4th edition, Corollary 3.3.4), there are $\kappa=\kappa(G)$ paths $P_1,\ldots, P_\kappa$, where for all $i$: $P_i$ starts at $x$ and ends at a $v_{j_i}\in C$, all other vertices of $P_i$ are in $V(G)\setminus(C\cup x)$, the $v_{j_i}$ are distinct, and $P_i$ and $P_\ell$ are internally disjoint for all $i\neq \ell$.

For each $i=1,\ldots,\kappa$, let $w_i=v_{{j_i}+1}$, i.e., the next vertex along $C$ from $v_{j_i}$.

No $w_i$ is adjacent to $x$, as otherwise we could delete the edge $(v_{j_i},w_i)$, and add the paths $P_i$ and $(w_i,x)$ to get a longer cycle in $G$. But then in the set of $\kappa+1$ vertices $\{x,w_1,\ldots,w_{\kappa}\}$, there must be a $w_i$ and $w_\ell$ that are adjacent. But now deleting from $C$ the edges $(v_{j_i},w_i)$ and $(v_{j_\ell},w_\ell)$, adding $(w_i,w_j)$ and the paths $P_i$ and $P_\ell$ gives a cycle in $G$ longer than $C$, a contradiction.