Bridge Obstructions to Cubic Edge Coloring

Why a Bridge Conflicts with Three Edge Colors

In a cubic graph, every vertex is incident with exactly three edges. A proper edge-coloring with three colors must therefore use each color exactly once at every vertex. This local condition has a useful global consequence: the edges of each color form a perfect matching. A bridge creates a cut with just one edge, and parity forces every perfect matching to use that edge. Since the three color classes are disjoint, that cannot happen.

All graphs in this tutorial are finite and simple. A graph is cubic if every vertex has degree \(3\). An edge is a bridge if deleting it increases the number of connected components. A matching is a set of edges no two of which share an endpoint; it is perfect if every vertex is incident with one of its edges. A proper three-edge-coloring assigns one of three colors to each edge so that edges sharing a vertex have different colors.

For the obstruction, consider the two vertex sets on either side of a bridge. Each side has an odd number of vertices. Then a perfect matching must cross the cut, and because the bridge is the only edge crossing it, that matching must contain the bridge. This requirement for all three color classes contradicts the fact that the bridge has only one color.

The Parity of the Two Sides

Let \(G\) be a connected cubic graph and let \(e=xy\) be a bridge. Deleting \(e\) splits \(G\) into two components. Write \(A\) for the vertex set of the component containing \(x\), and \(B\) for the vertex set of the component containing \(y\). Within \(G[A]\), vertex \(x\) has degree \(2\), since its third incident edge was \(e\); all other vertices of \(A\) still have degree \(3\). Thus the sum of the degrees in \(G[A]\) is \(3|A|-1\). A degree sum equals twice the number of edges, so it is even. Since \(3|A|-1\) is even, \(|A|\) is odd. The same argument gives that \(|B|\) is odd.

Proof. Let \(M\) be a perfect matching. Let \(E(A)\) denote the edges with both endpoints in \(A\), and let \(M\cap E(A)\) be the matching edges lying entirely inside \(A\). Each such edge covers two vertices of \(A\). Every other vertex of \(A\) must be covered by a matching edge crossing from \(A\) to its complement. There is only one graph edge available for such a crossing, namely \(e\). Therefore \[ |A|=2|M\cap E(A)|+\mathbf{1}_{\{e\in M\}}, \] where the indicator is \(1\) if \(e\in M\) and \(0\) otherwise. The first term is even, while \(|A|\) is odd. Hence the indicator must equal \(1\), so \(e\in M\). \(\square\)

The equation also describes the even case: if \(|A|\) is even, a perfect matching cannot use the sole crossing edge. The lemma relies on the matching being perfect and on there being exactly one crossing edge; without either condition, this parity conclusion need not hold.

The Bridge Obstruction Theorem

Proof. Suppose, to obtain a contradiction, that \(G\) has a proper three-edge-coloring with colors red, blue and green. By the key fact, the edges of each color form a perfect matching: call them \(M_{\mathrm{red}}, M_{\mathrm{blue}}\) and \(M_{\mathrm{green}}\). Let \(e\) be a bridge, and let \(A\) be either component’s vertex set after deleting \(e\). The degree-sum argument shows that \(|A|\) is odd, and \(e\) is the sole edge crossing from \(A\) to the rest of \(G\). The matching-parity lemma therefore forces \(e\) to belong to every perfect matching. In particular, \(e\) must belong to all three color classes. But a colored edge has exactly one color, so it belongs to only one color class. This contradiction proves that the coloring does not exist. \(\square\)

The same contradiction can be seen by looking at the bridge’s color. If \(e\) is red, then the red matching must use it, as parity requires. But parity also requires the blue perfect matching to use it and the green perfect matching to use it. The bridge cannot simultaneously have three different colors. The argument does not depend on which color is assigned to the bridge.

Common Pitfalls and the Scope of the Result

Pitfall: treating an odd side as if it could be matched internally. For the five-vertex side in the first example, an incorrect count might claim that two internal matching edges cover the side, writing \(5=2\cdot2\). The right-hand side is \(4\), not \(5\): one vertex is left uncovered. The correct count for a perfect matching is \(5=2k+1\), where the final \(1\) records a matching edge crossing the cut. Since the cut has only the bridge, that edge must be the bridge.

Pitfall: assuming the theorem goes both ways. The result proves that a bridge prevents a proper three-edge-coloring in a cubic graph. It does not prove that every cubic graph without a bridge has such a coloring. The example \(K_4\) verifies one bridgeless graph that does have a coloring, but a single example cannot establish a general converse.

Pitfall: omitting the perfect-matching step. It is not enough to say that three colors are available. The decisive condition is that the graph is cubic and the coloring is proper: those hypotheses force each color to occur exactly once at every vertex, making each color class a perfect matching. Without that fact, the parity lemma has no reason to apply to each color class.

The obstruction is useful because it turns a coloring question into a structural test. Before trying to find a three-edge-coloring of a cubic graph, one can check whether it has a bridge; if it does, the parity argument rules out every possible coloring at once. In the setting of Tait edge-colorings, this identifies a necessary structural condition, not a complete criterion for colorability.