• 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 ?

  • 2
    $\begingroup$ In the intro of this : math.mit.edu/~cb_lee/resource/HamiltonicityPancyclicity.pdf, they say "Let the independence number α(G) of a graph G be the order of a maximum independent set of G. A classical result of Chvatal and Erdos [4] says that every graph G whose vertex connectivity (denoted κ(G)) is at least as large as its independence number is Hamiltonian.". So I think there isn't one. $\endgroup$ – Manuel Lafond Oct 22 '14 at 19:12

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.