4
$\begingroup$

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.$

1 Answers 1

5

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:

Case 1

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:

Case 2

Since this cycle is longer than $C$, we have a contradiction.

  • 1
    May I ask about the source of these pictures?2015-01-07