Prove that if a graph $G$ is $k$-connected and $\alpha(G) \le k$ then $G$ is Hamiltonian. Where $\alpha(G) $ is the size of the largest independent set in $G.$
Prove that a graph is Hamiltonian
1 Answers
This is:
Chvátal-Erdős Theorem: Let $G$ be a $k$-connected graph with $n \geq 3$ vertices. If $\alpha(G)\leq k$ then $G$ is Hamiltonian.
It was proved in:
Chvátal V., Erdős P., A note on Hamiltonian circuits, Discrete Math. 2 (1972), 111-113. (pdf)
Here's a sketch of the proof. (Note: the result is only true when $G$ has $n \geq 3$ vertices.)
Step 1: If $k=1$, then $G=K_n$, which is Hamiltonian since $n \geq 3$. Now assume $k \geq 2$.
Step 2: Let $C$ be the largest cycle in $G$. If $C$ is not Hamiltonian, then there is a vertex $x$ outside of $C$. Since $G$ is $k$-connected, there are $k$ paths from $C$ to $x$ which are disjoint apart from $x$; call the terminal vertices $x_1,x_2,\ldots,x_k$.
If two of the $x_i$'s are next to each other, we can find a longer cycle as depicted below:
Since this cycle is longer than $C$, we have a contradiction.
Step 3: For each $x_i$, define its successor $y_i$ to be the vertex adjacent to $x_i$ when we go around $C$ in some fixed direction. Importantly, we can assume $\{y_i\}_{i=1}^k \cap \{x_i\}_{i=1}^k = \emptyset$ (otherwise, we're at a situation covered by Step 2).
Since $\alpha(G) \leq k$, there exists a pair of vertices in $\{y_i\}_{i=1}^k$ that are adjacent (otherwise $\{y_i\}_{i=1}^k \cup \{x\}$ is an independent set of size $k+1$).
Hence we can find a longer cycle as depicted below:
Since this cycle is longer than $C$, we have a contradiction.
-
1May I ask about the source of these pictures? – 2015-01-07