Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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