Bipartite Edge Coloring and Degree-Based Bounds

Why Vertex Degrees Force Edge Colors

In a proper edge coloring, two edges that share a vertex must receive different colors. Consequently, a vertex of large degree imposes a local requirement: all of its incident edges need separate colors. This gives a lower bound on the edge chromatic number, regardless of whether the graph is bipartite. For bipartite graphs, small examples often attain that bound, which makes the maximum degree a natural benchmark.

All graphs in this tutorial are finite and simple. A proper edge coloring assigns a color to each edge so that any two edges with a common endpoint have different colors. The edge chromatic number \(\chi'(G)\) is the least number of colors in a proper edge coloring of \(G\). A matching is a set of edges no two of which share an endpoint. Thus the edges of any one color in a proper edge coloring form a matching.

Definition: The maximum degree \(\Delta(G)\) is the largest degree of a vertex of \(G\). For a graph with no edges, set \(\chi'(G)=0\); then \(\Delta(G)=0\) as well.

A graph is bipartite if its vertex set can be partitioned into two sets \(X\) and \(Y\) so that every edge has one endpoint in each set. The parts may be empty. Bipartiteness does not change the local requirement at a vertex: all edges incident to that vertex still need different colors.

Two Lower Bounds

Theorem: Every finite simple graph \(G\) satisfies \(\chi'(G)\geq \Delta(G)\).

Proof. If \(G\) has no edges, the stated convention gives \(\chi'(G)=0=\Delta(G)\). Otherwise, choose a vertex \(v\) with degree \(\Delta(G)\). In any proper edge coloring, each of the \(\Delta(G)\) edges incident to \(v\) must have a different color, because every pair of those edges shares \(v\). Therefore the coloring uses at least \(\Delta(G)\) colors. This holds for every proper edge coloring, so the minimum number of colors also satisfies \(\chi'(G)\geq\Delta(G)\). \(\square\)

The same argument can be phrased in terms of matching color classes. Each color class is a matching, so it can contain at most one edge incident to any particular vertex. The bound comes from the vertex with the most incident edges, not from the average degree or the total number of edges alone.

Theorem: If \(G\) has \(n\geq 2\) vertices and \(m\) edges, then \(\chi'(G)\geq \left\lceil m/\lfloor n/2\rfloor\right\rceil\). If \(G\) is bipartite with parts \(X,Y\), both nonempty, then also \(\chi'(G)\geq \left\lceil m/\min(|X|,|Y|)\right\rceil\).

Proof. A matching on \(n\) vertices uses two distinct vertices for each edge. It therefore has at most \(\lfloor n/2\rfloor\) edges. If a proper edge coloring uses \(q\) colors, its \(q\) color classes partition the \(m\) edges, and each class has at most \(\lfloor n/2\rfloor\) edges. Hence \(m\leq q\lfloor n/2\rfloor\). Since \(\lfloor n/2\rfloor>0\) for \(n\geq2\), division and the fact that \(q\) is an integer give \(q\geq\lceil m/\lfloor n/2\rfloor\rceil\). Taking the minimum over proper colorings proves the first bound. For a bipartite graph, each matching uses at most one vertex from \(X\) and at most one from \(Y\) per edge. Its size is therefore at most \(\min(|X|,|Y|)\). Replacing the matching-size bound by this sharper bound gives \(m\leq q\min(|X|,|Y|)\), and hence the second inequality. If \(m=0\), both bounds are zero and hold. \(\square\)

The edge-count bounds can complement the maximum-degree bound, but need not be as strong. The degree bound uses the edges concentrated at one vertex; the matching-size bound uses the total number of edges and the number of vertices available to each color class. In either case, a lower bound does not by itself produce a coloring using that many colors.

Worked Bipartite Examples

Worked Example: A Star Attains the Degree Bound

Let \(G=(V,E)\) have \(V=\{c,a,b,d\}\) and \(E=\{ca,cb,cd\}\). This is the star \(K_{1,3}\), which is bipartite with parts \(\{c\}\) and \(\{a,b,d\}\).

The center \(c\) has degree \(3\), and each other vertex has degree \(1\), so \(\Delta(G)=3\). The degree lower bound requires at least three colors. Give \(ca\) red, \(cb\) blue, and \(cd\) green. Edges of the same color do not meet: each color class contains just one edge. This is a proper coloring using three colors, so \(\chi'(G)\leq3\); together with the lower bound, \(\chi'(G)=3=\Delta(G)\).

Check: the three incident edges at \(c\) have three distinct colors, so fewer than three colors cannot work. The displayed coloring uses exactly three, verifying both inequalities.

Worked Example: A 4-Cycle Needs Two Colors

Let \(G=(V,E)\) have \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd,da\}\). This is the cycle \(C_4\), and it is bipartite with parts \(\{a,c\}\) and \(\{b,d\}\).

Every vertex has degree \(2\), so \(\Delta(G)=2\) and at least two colors are required. Color \(ab\) and \(cd\) red, and color \(bc\) and \(da\) blue. The two red edges have no common endpoint, and neither do the two blue edges. Every edge appears exactly once in the assignment, so it is a proper edge coloring with two colors.

Check: at each of \(a,b,c,d\), one incident edge is red and the other is blue. Thus the coloring is proper, and the lower bound confirms \(\chi'(G)=2=\Delta(G)\).

Worked Example: The Edge-Count Bound Matches the Degree Bound

Let \(G=(V,E)\) have \(V=\{x,y,a,b,c\}\) and \(E=\{xa,xb,xc,ya,yb,yc\}\). This is \(K_{2,3}\), with parts \(X=\{x,y\}\) and \(Y=\{a,b,c\}\). The degrees of \(x,y\) are \(3\), and the degrees of \(a,b,c\) are \(2\). Therefore \(\Delta(G)=3\), with \(m=6\) and \(n=5\).

The degree bound gives \(\chi'(G)\geq3\). The bipartite edge-count bound also gives \(\chi'(G)\geq\lceil 6/\min(2,3)\rceil=\lceil6/2\rceil=3\). Now color \(xa,yb\) red; \(xb,yc\) blue; and \(xc,ya\) green. Each color class consists of two edges with disjoint endpoints. The three classes partition the six listed edges, so this is a proper three-coloring.

Check: each of \(x\) and \(y\) is incident to one red, one blue and one green edge. Each of \(a,b,c\) is incident to two edges with different colors. The coloring uses three colors and the lower bound is three, so \(\chi'(G)=3=\Delta(G)\).

Worked Example: A Matching-Size Bound Can Be Weaker

Let \(G=(V,E)\) have \(V=\{u,v,w,1,2,3\}\) and \(E=\{u1,u2,u3,v1,v2,w1\}\). This is bipartite with parts \(X=\{u,v,w\}\) and \(Y=\{1,2,3\}\). The degrees on \(X\) are \(3,2,1\), and the degrees on \(Y\) are \(3,2,2\). Thus \(\Delta(G)=3\), and the degree bound gives \(\chi'(G)\geq3\).

There are \(m=6\) edges and \(n=6\) vertices. The general matching-size bound gives only \(\chi'(G)\geq\lceil6/\lfloor6/2\rfloor\rceil=\lceil6/3\rceil=2\). For an explicit coloring, use red on \(\{u1,v2\}\), blue on \(\{u2,v1\}\), and green on \(\{u3,w1\}\). Within each color class the endpoints are distinct, and together the three classes contain every edge exactly once. Hence this is a proper coloring using three colors.

Check: the coloring gives \(\chi'(G)\leq3\), while the vertex \(u\), incident to \(u1,u2,u3\), forces \(\chi'(G)\geq3\). Therefore \(\chi'(G)=3=\Delta(G)\). The general edge-count bound is valid here, but its value \(2\) is weaker than the degree bound \(3\).

What the Examples Show—and What They Do Not

In each example, an explicit coloring establishes an upper bound on \(\chi'(G)\), while a degree or matching-size argument establishes a lower bound. When the two bounds agree, the edge chromatic number is determined exactly. This is the right way to use examples: verify both that the proposed coloring works and that fewer colors are impossible.

Several common errors arise when applying these bounds:

Reversing the degree inequality. The fact that \(\Delta(G)\) colors are necessary does not say that \(\Delta(G)\) colors always suffice. In the star example, the lower bound becomes exact only after a coloring with three colors has been exhibited.
Counting a color class as if it could use every edge. A color class must be a matching. In \(K_{2,3}\), each color can cover at most two edges, because each matching uses at most two vertices from the part of size two.
Checking only the number of colors. An assignment using three labels is not automatically a proper coloring. For every label, its edges must be checked for shared endpoints; every edge must also receive a label.
Treating the edge-count bound as always decisive. In the last example it gives \(2\), whereas the vertex of degree \(3\) proves that at least \(3\) colors are needed. The two lower bounds measure different constraints.

The examples show that bipartite graphs can attain the degree lower bound, including graphs with unequal part sizes and with vertices of different degrees. They do not establish that every bipartite graph attains it: an example verifies a particular graph, not an entire class. The general statement that every finite bipartite graph has edge chromatic number equal to its maximum degree is Kőnig’s line-coloring theorem; its proof belongs with the later treatment of that theorem.

Check Your Understanding

For each question, distinguish a lower bound from an explicit coloring that attains it.

Let \(G=(V,E)\) have \(V=\{r,s,t,u\}\) and \(E=\{rs,st,tu\}\). Find \(\Delta(G)\) and give a proper edge coloring using that many colors, or explain why one cannot exist.
Explain why every color class in a proper edge coloring is a matching, and use this fact to prove the general bound \(\chi'(G)\geq\lceil m/\lfloor n/2\rfloor\rceil\) for \(n\geq2\).
For \(K_{2,4}\), compute the maximum degree and the bipartite matching-size lower bound. Do the bounds agree?
A student gives a proper edge coloring of a graph using \(\Delta(G)+1\) colors. Does that prove \(\chi'(G)=\Delta(G)+1\)? State what additional information would be needed.