Independent Sets Along a Hamiltonian Cycle
A Hamiltonian cycle visits every vertex exactly once before returning to its start. If a set of vertices is independent, no two of them are adjacent; in particular, no edge of a Hamiltonian cycle can join two vertices of that set. Each selected vertex therefore uses two different cycle edges, and those edges must also be incident to vertices outside the set. Counting these incidences gives a necessary condition for Hamiltonicity that applies whether or not the graph is bipartite.
Throughout, graphs are finite and simple. A set \(S\subseteq V(G)\) is independent if no edge of \(G\) has both endpoints in \(S\). The independence number \(\alpha(G)\) is the largest size of an independent set in \(G\). A graph is Hamiltonian if it contains a cycle that includes every vertex. Thus a Hamiltonian graph has at least three vertices, and such a cycle has exactly \(n=|V(G)|\) edges.
Proof. Fix a Hamiltonian cycle \(C\) in \(G\), and let \(S\) be any independent set. Each vertex of \(S\) is incident with exactly two edges of \(C\). Since \(S\) is independent, neither endpoint pair of a cycle edge lies entirely in \(S\). Consequently, the two cycle edges at each vertex of \(S\) are distinct from the two cycle edges at every other vertex of \(S\): an edge counted at two vertices would have both endpoints in \(S\). Hence exactly \(2|S|\) distinct edges of \(C\) are incident with \(S\). The cycle has \(n\) edges in total, so \(2|S|\le n\). This holds for every independent set \(S\), including the empty set, and therefore \(2\alpha(G)\le n\). Since \(\alpha(G)\) is an integer, \(\alpha(G)\le\lfloor n/2\rfloor\). \(\square\)
The proof uses edges of the Hamiltonian cycle, not all the edges of \(G\). Extra edges, or chords, do not affect the count. Nor does the proof require every vertex outside \(S\) to be selected: it requires only that the \(2|S|\) distinct cycle edges fit among the \(n\) edges of the cycle.
When the Bound Is Tight
Proof. Write \(k=|S|=n/2\), and list the vertices of \(S\) in their order around \(C\). Since \(n\ge3\) and \(n\) is even, \(n\ge4\), so \(k\ge2\). For each consecutive pair of listed vertices, including the last and first pair around the cycle, let the gap be the number of cycle edges from one to the next. No gap can be \(1\), because then its two endpoints would be adjacent and both in \(S\). Thus each of the \(k\) gaps is at least \(2\). Their sum is \(n=2k\), the total number of edges of \(C\). If any gap were greater than \(2\), their sum would exceed \(2k\); therefore every gap is exactly \(2\). Between every two consecutive vertices of \(S\) there is exactly one vertex outside \(S\), which is precisely alternation around \(C\). \(\square\)
This proposition describes equality on the chosen cycle. It does not say that the graph has no additional edges: a Hamiltonian graph may have chords, but an equality-size independent set cannot contain both endpoints of any such chord. Conversely, if the vertices of a Hamiltonian cycle alternate between \(S\) and its complement and \(S\) is independent in the whole graph, then \(|S|=n/2\), so the bound is attained.
Worked Example: The Bound Is Attained on a Six-Cycle
Let \(G\) have vertex set \(V=\{1,2,3,4,5,6\}\) and edge set \(E=\{12,23,34,45,56,61\}\). This is the cycle \(C_6\), and its listed edges form a Hamiltonian cycle.
Take \(S=\{1,3,5\}\). None of the six listed edges has both endpoints in \(S\), so \(S\) is independent and \(|S|=3\). The theorem gives \(\alpha(G)\le\lfloor 6/2\rfloor=3\); the exhibited set gives \(\alpha(G)\ge3\). Therefore \(\alpha(G)=3\).
Check: the cycle edges incident with \(S\) are \(12,61,23,34,45,56\), all six edges. The incidence count is \(2|S|=2\cdot3=6=|E(C_6)|\), as required for equality. The vertices of \(S\) alternate with \(2,4,6\) around the cycle.
Using a Large Independent Set to Rule Out Hamiltonicity
The theorem is a necessary condition: if \(\alpha(G)>\lfloor n/2\rfloor\), then \(G\) cannot be Hamiltonian. To use this as a certificate, it is enough to exhibit an independent set whose size exceeds the bound; there is no need to determine \(\alpha(G)\) exactly. In examples where we do determine the exact value, we verify both a lower bound (by exhibiting a set) and an upper bound (by showing no larger set is possible).
Worked Example: A Connected Graph with Too Many Independent Vertices
Let \(G\) have vertex set \(V=\{a,b,c,d,e,x,y,z\}\). Its edge set consists of all edges from \(\{a,b,c,d,e\}\) to \(\{x,y,z\}\), together with the triangle edges \(xy,yz,zx\). Explicitly, these are \(ax,ay,az,bx,by,bz,cx,cy,cz,dx,dy,dz,ex,ey,ez,xy,yz,zx\). The graph is simple and connected.
The set \(S=\{a,b,c,d,e\}\) is independent, because there are no edges between its vertices. Hence \(\alpha(G)\ge5\). In fact, \(\alpha(G)=5\): an independent set containing any of \(x,y,z\) cannot contain any of \(a,b,c,d,e\), since each of \(x,y,z\) is adjacent to all five. It can contain at most one of \(x,y,z\), because those three form a triangle. Such an independent set has size at most \(1\); one containing none of \(x,y,z\) has size at most \(5\).
Here \(n=8\), so a Hamiltonian graph could have independence number at most \(\lfloor8/2\rfloor=4\). But \(\alpha(G)=5\), and \(5>4\). Thus \(G\) is not Hamiltonian.
Check: a Hamiltonian cycle would have \(8\) edges, while the five vertices of \(S\) would require \(2\cdot5=10\) distinct cycle edges incident with them. Since \(10>8\), such a cycle cannot exist. This is the same obstruction as the independence-number bound, expressed directly as a cycle-edge count.
Worked Example: Passing the Bound Does Not Prove Hamiltonicity
Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,23,34\}\), so \(G=P_4\). The set \(\{1,3\}\) is independent, giving \(\alpha(G)\ge2\). No set of three vertices is independent: if one omits \(1\), the remaining vertices include the edge \(23\); if one omits \(2\), they include \(34\); if one omits \(3\), they include \(12\); and if one omits \(4\), they include \(12\). Therefore \(\alpha(G)=2\).
The necessary bound gives \(\alpha(G)\le\lfloor4/2\rfloor=2\), so \(G\) passes this test. Nevertheless, \(G\) is not Hamiltonian: vertices \(1\) and \(4\) each have only one incident edge, while a vertex on a cycle must be incident with two distinct cycle edges. Thus the independent-set bound can rule out Hamiltonicity when it fails, but passing it does not establish Hamiltonicity.
Check: the exact value \(\alpha(G)=2\) equals the bound \(4/2=2\), yet the graph has no Hamiltonian cycle. The conclusion is not a contradiction: the theorem gives a necessary condition, not a sufficient one.
Common Counting Pitfall
When counting cycle incidences, it matters that the chosen set is independent. For example, let \(C_4\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\). The set \(\{1,2\}\) is not independent. Counting two cycle edges at each of its vertices gives \(2\cdot2=4\) incidences, but there are only three distinct cycle edges incident with the set: \(12,23,41\). Edge \(12\) was counted twice because both its endpoints lie in the set.
The correction is not to apply the theorem to this set: the theorem concerns independent sets. For the independent set \(\{1,3\}\), the four incident cycle edges are \(12,41,23,34\), each counted once. In general, independence guarantees that no cycle edge has both endpoints in the set, which is exactly what makes the count \(2|S|\) a count of distinct edges.
The obstruction is useful because it is quick to check and gives a concrete certificate: a set of more than half the vertices with no internal edges. Its limitation is equally important. A small independence number, even one at the maximum allowed value, does not supply a Hamiltonian cycle; other structural obstructions may still prevent one.
Check Your Understanding
For each question, distinguish a necessary condition from a sufficient one, and show the relevant count.
- Let \(G\) be Hamiltonian on \(11\) vertices. What is the largest possible value of \(\alpha(G)\)?
- A graph on \(12\) vertices contains an independent set of size \(7\). What conclusion follows about Hamiltonicity?
- On a fixed Hamiltonian cycle of order \(10\), an independent set has size \(5\). What must its positions around the cycle look like?
- Explain why the edges of a Hamiltonian cycle incident with an independent set \(S\) number \(2|S|\), rather than fewer.
- Give a reason, using the graph in the third worked example, that satisfying the independence-number bound does not prove a graph Hamiltonian.