Cut Vertices And Bridges As Obstructions

Why Cut Vertices and Bridges Matter

A Hamiltonian cycle must visit every vertex exactly once before returning to its start. That requirement makes certain kinds of bottlenecks impossible: a cycle cannot pass through one vertex twice to join separated regions, and it cannot use a single edge as the only connection between two sides. We will make both statements precise and prove them from the way a cycle uses vertices and crosses a partition.

All graphs in this tutorial are finite and simple. A graph is connected if every pair of its vertices is joined by a path. A component is a maximal connected subgraph; write \(c(G)\) for the number of components, with \(c(G)=0\) when \(V(G)=\varnothing\). A graph is Hamiltonian if it contains a cycle that includes every vertex. Thus a Hamiltonian graph has at least three vertices.

Since \(G\) is connected in these definitions, a cut vertex disconnects the remaining vertices, while a bridge disconnects the graph when removed. A cut vertex is a bottleneck at a vertex; a bridge is a bottleneck at an edge. The claim is that neither can occur in a Hamiltonian graph.

What a Spanning Cycle Leaves Behind

Proof. Let \(C\) be a cycle containing every vertex of \(G\), and let \(v\in V(G)\). Write the vertices of \(C\), starting at \(v\), in cyclic order as \(v,v_1,v_2,\dots,v_{n-1},v\). After deleting \(v\), the remaining cycle edges include the path \(v_1v_2\cdots v_{n-1}\), which contains every vertex of \(G-v\). Therefore any two vertices of \(G-v\) are joined by a subpath of this path, so \(G-v\) is connected. \(\square\)

This is also a useful way to think about the obstruction. If deleting a vertex separates the graph into multiple components, a cycle that visits all of them would have to leave one component through that vertex and later return through the same vertex. But a cycle visits each vertex only once, so it cannot do this.

Proof. Traverse the cycle in order and record, for each vertex, whether it belongs to \(S\) or to \(V(G)\setminus S\). Each edge crossing between the two sides changes the recorded membership. Because the traversal returns to its starting vertex, the number of changes is even. Since both sides contain a vertex of the cycle, at least one change occurs; an even positive number is at least two. Thus at least two cycle edges cross the partition. \(\square\)

For a vertex partition, the set of edges with endpoints on opposite sides is sometimes called its edge boundary. The lemma says that a cycle meeting both sides cannot cross an edge boundary just once. A bridge would create exactly such a one-edge boundary when its deletion separates the graph.

The Obstructions Theorem

Proof. Suppose \(G\) is Hamiltonian. It is connected, since its spanning cycle connects every pair of vertices by a route along the cycle. By the first lemma, for every vertex \(v\), the graph \(G-v\) is connected. Hence \(c(G-v)=1=c(G)\), so \(v\) is not a cut vertex. This holds for every \(v\).

Now suppose, for a contradiction, that \(G\) has a bridge \(e\). The graph \(G-e\) is disconnected, so its vertices can be partitioned into a nonempty set \(S\) and its nonempty complement \(V(G)\setminus S\), with no edge of \(G-e\) crossing between them. In \(G\), the only edge that can cross this partition is \(e\): any other crossing edge would still be present in \(G-e\) and would join the two sides. But a Hamiltonian cycle contains every vertex, so it meets both sides. By the second lemma, it must use at least two edges crossing the partition. There is only one such edge in \(G\), a contradiction. Therefore \(G\) has no bridge. \(\square\)

The bridge argument can also be read as a test on any proposed spanning cycle: every nontrivial partition must have at least two crossing edges available to the cycle. A bridge offers only one, so it cannot belong to a spanning cycle—and, more strongly, a graph with a bridge cannot have any spanning cycle.

Worked Examples

Common Pitfalls

Do not confuse breaking a cycle with disconnecting a graph. A common incorrect argument is: “Deleting an edge of a cycle breaks the cycle, so that edge is a bridge.” In the first example, deleting \(12\) does break the closed cycle, but the remaining edges form the connected path \(2,3,4,5,6,1\). A bridge is defined by whether the whole graph becomes disconnected, not by whether a particular cycle is broken.

One necessary condition is not a characterization. Having no cut vertex and no bridge does not guarantee Hamiltonicity. For a concrete example, let \(G=(V,E)\) have \(V=\{x,y,a,b,c\}\) and \(E=\{xa,xb,xc,ya,yb,yc\}\). Each edge lies on a 4-cycle: for example, \(xa\) lies on \(x,a,y,b,x\). Hence deleting any edge leaves a route between its endpoints, and no edge is a bridge. Deleting \(x\) leaves the connected star with center \(y\); deleting \(y\) leaves the connected star with center \(x\); deleting any one of \(a,b,c\) leaves the other two joined to both \(x\) and \(y\). So there is no cut vertex either.

Nevertheless, this graph is not Hamiltonian. Each of \(a,b,c\) has exactly two incident edges, so any cycle containing that vertex must use both of them. A cycle through all three would therefore use all three edges incident to \(x\), namely \(xa,xb,xc\). But a cycle uses exactly two incident edges at each of its vertices. This contradiction rules out a spanning cycle. Thus the absence of cut vertices and bridges is a necessary test, not a sufficient one.

Using the Tests

To rule out Hamiltonicity, it is enough to find one cut vertex or one bridge. The relevant calculation is local and concrete: delete the candidate vertex or edge, then check whether the number of components increases. If it does, the graph cannot be Hamiltonian. If neither obstruction is present, this particular test gives no conclusion; other necessary conditions or sufficient criteria may still be useful.

• For a cut-vertex test, compare \(c(G-v)\) with \(c(G)\).
• For a bridge test, compare \(c(G-e)\) with \(c(G)\), or find a partition crossed by exactly one edge.
• Do not infer Hamiltonicity just because every such deletion leaves the graph connected.