Kőnig’s Line Coloring Theorem

Edge Coloring and the Theorem

In an edge coloring, edges that share an endpoint must receive different colors. Thus every color class is a matching: a set of edges no two of which have a common endpoint. The aim here is to determine exactly how many colors are needed for a bipartite graph, including when parallel edges are present. The key idea is to enlarge the graph to a regular bipartite multigraph, decompose that graph into perfect matchings, and then discard the added edges.

We use the convention \(\chi'(G)=0\) when \(E=\varnothing\), including when \(V=\varnothing\). Write \(\Delta(G)\) for the maximum degree, where parallel edges contribute separately. The theorem says that for every finite bipartite multigraph, \(\chi'(G)=\Delta(G)\). The lower bound follows because the edges incident with a vertex of maximum degree must all receive distinct colors. The main work is proving that \(\Delta(G)\) colors always suffice.

A Matching Existence Fact

We first establish the matching fact needed for the regular decomposition. For a bipartite multigraph with parts \(A,B\), let \(N(S)\) be the set of vertices in \(B\) adjacent to at least one vertex of \(S\subseteq A\). A matching saturates \(A\) if it has an edge incident with every vertex of \(A\).

Proof. If a matching saturates \(A\), its edges assign distinct neighbors in \(B\) to the vertices of every \(S\subseteq A\), so \(|N(S)|\ge |S|\). For the converse, use induction on \(|A|\). If \(|A|=0\), the empty matching saturates \(A\). Suppose \(|A|\ge1\) and the condition holds.

First suppose there is a nonempty proper subset \(S\subset A\) with \(|N(S)|=|S|\). The condition holds for all subsets of \(S\), so induction gives a matching between \(S\) and \(N(S)\) saturating \(S\). For any \(T\subseteq A\setminus S\), applying the condition to \(S\cup T\) gives \(|N(S)\cup N(T)|\ge |S|+|T|\). Since \(|N(S)|=|S|\), this implies \(|N(T)\setminus N(S)|\ge |T|\). Thus the graph on \(A\setminus S\) and \(B\setminus N(S)\) satisfies the condition; induction gives a matching saturating \(A\setminus S\) there. These two matchings have disjoint endpoints and together saturate \(A\).

Now suppose no such \(S\) exists. Every nonempty proper subset \(T\subset A\) then satisfies \(|N(T)|\ge |T|+1\). Choose \(a\in A\). The condition for \(\{a\}\) guarantees a neighbor \(b\in B\), so choose one edge \(ab\) and remove \(a,b\). For every nonempty \(T\subseteq A\setminus\{a\}\), \(T\) is a proper subset of \(A\), so \(|N(T)|\ge |T|+1\); deleting \(b\) removes at most one neighbor, leaving at least \(|T|\). The empty subset also satisfies the condition. Induction gives a matching saturating \(A\setminus\{a\}\) after the deletion. Adding \(ab\) gives a matching saturating \(A\). The argument works for \(|A|=1\) as well: after deleting \(a,b\), the empty matching saturates the empty remaining part. \(\square\)

Regular Bipartite Multigraphs Split into Matchings

Proof. Let its parts be \(A,B\). Counting edges by their endpoints in each part gives \(r|A|=|E|=r|B|\), so \(|A|=|B|\). For any \(S\subseteq A\), the \(r|S|\) edges incident with \(S\) all end in \(N(S)\). The total number of edges incident with vertices of \(N(S)\) is \(r|N(S)|\), so \(r|S|\le r|N(S)|\). Since \(r\ge1\), \(|S|\le |N(S)|\). By Hall’s condition there is a matching saturating \(A\); because \(|A|=|B|\), it also saturates \(B\), and is perfect. Remove its edges. Each vertex loses exactly one incident edge, leaving an \((r-1)\)-regular bipartite multigraph on the same parts. Repeating this argument for each positive degree gives a perfect matching at every stage until degree zero. These \(r\) matchings are disjoint and account for all edges, since after their removal every degree is zero. \(\square\)

Balancing and Filling Degree Deficits

A general bipartite multigraph need not have equally sized parts or equal degrees, so it need not itself be regular. We enlarge it without changing the original edges. Let \(D=\Delta(G)\). If \(D=0\), there are no edges and the theorem is already settled. Assume \(D\ge1\), with parts \(X,Y\). Add enough new vertices to the smaller part that the two parts have the same size \(N=\max(|X|,|Y|)\). These new vertices are called dummy vertices. The enlarged parts each have size \(N\), and all original degrees are at most \(D\).

For each vertex \(w\) in the enlarged graph, its degree deficit is \(D-\deg(w)\), a nonnegative integer. Count the deficits on each side. If the original graph has \(m\) edges, the sum of degrees on either side before adding dummy vertices is \(m\), because each edge has exactly one endpoint on that side. Adding dummy vertices contributes degree zero. Hence the sum of deficits on each side is \(ND-m\). The two sides therefore have equal total deficit.

For every vertex, make as many available places as its deficit. Pair the places on the \(X\)-side with those on the \(Y\)-side, and add an edge for each paired pair of places. Equal total deficits ensure that this pairing uses every place. Parallel edges are allowed, so no restriction prevents adding an edge between vertices already adjacent. Each vertex receives exactly its deficit number of new incidences, making the enlarged graph \(D\)-regular. Its vertex parts are still bipartite and have equal size.

Kőnig’s Line Coloring Theorem

Proof. First suppose \(\Delta(G)=0\). Every vertex has degree zero, so \(E(G)=\varnothing\). The empty coloring uses zero colors, and by the stated convention \(\chi'(G)=0=\Delta(G)\).

Now suppose \(D=\Delta(G)\ge1\). Regularize \(G\) as described above, obtaining a \(D\)-regular bipartite multigraph with equal part sizes. By the proposition, its edges split into \(D\) perfect matchings. Give each matching its own color, then restrict this coloring to the original edges. A subset of a matching is still a matching, so each resulting color class is a valid edge color class in \(G\). Thus \(\chi'(G)\le D\).

For the reverse inequality, choose a vertex \(v\) with \(\deg(v)=D\). Any two distinct edges incident with \(v\), including parallel edges, share an endpoint and must receive different colors. Therefore every proper edge coloring uses at least \(D\) colors, giving \(\chi'(G)\ge D\). Combining the bounds yields \(\chi'(G)=D=\Delta(G)\). \(\square\)

Why the Bipartite Hypothesis Matters

The proof depends on the ability to make a regular bipartite multigraph and then find a perfect matching at each degree level. Bipartiteness is what gives the neighborhood condition in the regular case: the \(r|S|\) incidences from \(S\) must fit among the \(r|N(S)|\) incidences at its neighbors. Without that structure, this argument does not provide the same conclusion.

A common mistake is to say that each color class is a matching and conclude that a graph of maximum degree \(D\) can be colored with \(D\) colors. That conclusion does not follow from the definition: it is necessary to prove that the edges can actually be partitioned into \(D\) matchings. Kőnig’s theorem supplies that existence proof for bipartite multigraphs. Another mistake is to ignore multiplicity. Two parallel edges have the same pair of endpoints, so they are adjacent edges and must receive different colors; they also each contribute one to the degree.