On the Condition for Hamiltonian Graph

Question

In the Graph Theory lecture, I took an exercise as follows: For $\emptyset \neq S \subseteq V(G)$, let $t(S) = \lvert\overline{S} \cap N(S) \rvert / \lvert \overline{S} \rvert$. Let $\theta(G) = \min t(S)$. It is known that if $\theta(G) \lvert V(G) \rvert \geq \alpha(G)$, then $G$ is hamiltonian. Prove that $\kappa(G) \geq \alpha(G)$ implies $\theta(G) \lvert V(G) \rvert \geq \alpha(G)$.

I tried to solve this question by using the contradiction, that is, assume there is a graph $G$ that satisfies $\kappa(G) \geq \alpha(G)$ but $\theta(G) \lvert V(G) \rvert < \alpha(G)$ and taking the graph with smallest number of vertices among such graphs. But I am stuck in how to relate the value of $\theta(G)$ with $\kappa(G)$. Could someone give me a hint?

Answer 1

Your idea is not bad at all; it is reminiscent of the proof of Dirac's theorem (also about Hamiltonian graphs) where we take an edge-maximal counterexample. The following proof could be rephrased in terms of contradiction, but it is just as easy to write it as a direct proof, and hence this is what I've done. As a hint, I'd say to consider how the nature of $t(S)$ changes as we vary $\lvert S \rvert$ (keeping in mind the hypothesis of $\kappa(G) \geq \alpha(G)$); there is a certain threshold (dependent on $\kappa(G)$) before which the calculation of $t(S)$ is "trivial". Find a convenient inequality for $t(S)$ which holds past this threshold, and it should then be clear how to prove the desired statement.

Let $G$ be a graph of order $n$, $\emptyset \neq S \subseteq V(G)$, and suppose $\kappa(G) \geq \alpha(G)$. First, observe that whenever $\lvert S \rvert \geq n - \kappa(G)$, we have $t(S) = \frac{\lvert\overline{S} \cap N(S) \rvert}{\lvert \overline{S} \rvert} = 1$. On the other hand, when $\lvert S \rvert < n - \kappa(G)$, we have $t(S) = \frac{\lvert\overline{S} \cap N(S) \rvert}{\lvert \overline{S} \rvert} \geq \frac{\kappa(G)}{n - \lvert S \rvert}$ (neither of the previous 2 statements are immediately obvious; double-check the hypotheses, draw some examples, think about it more, and comment if you still aren't sure why they hold). Since $S$ is nonempty, $n > n - \lvert S \rvert$ which, combined with the above, yields $n \cdot t(S) > \kappa(G)$. Since $S$ was arbitrary, we may conclude that $\kappa(G) \geq \alpha(G)$ implies $n \cdot \theta(G) \geq \alpha(G)$, as desired.

Remark: I remember completing this very exercise when I was studying graph theory in school, and the main takeaway was that the result in the exercise (that $n \cdot \theta(G) \geq \alpha(G)$ implies $G$ is Hamiltonian; often known as Lu's theorem) is strictly stronger than the well-known theorem of Chvátal and Erdős (that $\kappa(G) \geq \alpha(G)$ implies $G$ is Hamiltonian (whenever $G \neq K_2$)). I found this quite interesting, even though the value $\theta(G)$ is not easy to compute in most cases. Nice exercise, thanks for asking it.