From a Degree Bound to a Coloring
An edge coloring assigns colors to edges so that edges sharing a vertex receive different colors. To construct an optimal coloring, it is not enough to use few colors: we also need to certify that the assignment is proper and that no coloring can use fewer. For bipartite graphs, Kőnig’s line coloring theorem supplies the existence guarantee. For a particular graph, a list of matching color classes supplies a direct, checkable certificate.
Throughout, graphs are finite and simple unless stated otherwise. A bipartite graph \(G=(V,E)\) has a partition \(V=X\cup Y\), with \(X\cap Y=\varnothing\), such that every edge has one endpoint in each part. A matching is a set of edges no two of which share an endpoint. A proper edge coloring is an assignment of colors to edges in which any two edges sharing a vertex have different colors. The set of edges assigned one color is a color class.
A proper coloring has matching color classes: if two edges of one color shared an endpoint, the coloring would not be proper. Conversely, assigning a different color to each of several matchings gives a proper coloring, provided the matchings partition the edge set. This gives a practical form for a coloring certificate.
Proof. Suppose first that a proper edge coloring uses at most \(k\) colors. For each color, take the set of edges assigned that color. No two edges in this set share an endpoint, by properness, so each set is a matching. Each edge receives exactly one color, so these color classes are disjoint and their union is \(E\). If a color is unused, omit its empty class; thus there are at most \(k\) matchings. Conversely, suppose \(E\) is partitioned into at most \(k\) matchings. Assign a distinct color to each matching. Any two edges with the same color belong to one matching, so they do not share an endpoint. The resulting coloring is proper. If \(E=\varnothing\), the empty partition uses zero colors and satisfies the statement for every \(k\geq0\). \(\square\)
Certifying Optimality
At a vertex of degree \(d(v)\), all \(d(v)\) incident edges need distinct colors. Consequently, the maximum degree is a lower bound on the number of colors. The useful goal is therefore to find a partition into exactly \(\Delta(G)\) matchings.
For bipartite graphs, the existence of such a partition is guaranteed by Kőnig’s line coloring theorem, also called Kőnig’s edge-coloring theorem. This is a standard result established in the earlier material on bipartite edge coloring. The statement includes graphs with isolated vertices: they do not add edges to color or increase the maximum degree. For an edgeless graph, the theorem’s equality reads \(0=0\).
The theorem guarantees that a coloring exists, but an explicit construction must still identify its color classes. When checking a proposed construction, verify three things: each listed class is a matching; the classes are pairwise disjoint; and their union is the entire edge set. If there are \(\Delta(G)\) classes, the degree lower bound then proves that the coloring is optimal.
Proof. Giving each of the \(\Delta(G)\) matchings its own color produces a proper coloring by the proposition, so \(\chi'(G)\leq\Delta(G)\). If \(G\) has an edge, some vertex has degree \(\Delta(G)\), and its incident edges require \(\Delta(G)\) distinct colors; hence \(\chi'(G)\geq\Delta(G)\). The two inequalities give equality. If \(G\) has no edges, both quantities are zero by convention, so equality holds in that case as well. \(\square\)
This certificate proves optimality for the specific graph without searching through all possible colorings. In the examples below, the matching classes are written out explicitly, and the number of edges and degrees are checked independently.
Worked Constructions
Worked Example: A Nearly Complete Bipartite Graph
Let \(G\) have parts \(X=\{a,b,c\}\) and \(Y=\{1,2,3\}\), with edge set \(E=\{a1,a2,a3,b1,b2,b3,c1,c3\}\). Find an optimal edge coloring.
The degrees on the \(X\)-side are \(\deg(a)=3\), \(\deg(b)=3\), and \(\deg(c)=2\). On the \(Y\)-side, the incident edges give \(\deg(1)=3\), \(\deg(2)=2\), and \(\deg(3)=3\). Thus \(\Delta(G)=3\), so at least three colors are required.
Partition the edges into the following classes:
| Color | Edges assigned that color |
|---|---|
| 1 | \(\{a1,b2,c3\}\) |
| 2 | \(\{a2,b3,c1\}\) |
| 3 | \(\{a3,b1\}\) |
Each class is a matching: in color 1 the \(X\)-endpoints are \(a,b,c\) and the \(Y\)-endpoints are \(1,2,3\); the same endpoint check holds for color 2; in color 3 the endpoints are \(a,b\) and \(3,1\), all distinct. The edge lists are disjoint and together contain \(3+3+2=8\) edges, exactly the eight edges in \(E\).
Check: The degree sum on \(X\) is \(3+3+2=8\), and on \(Y\) it is \(3+2+3=8\), agreeing with the edge count on each side. The coloring uses three colors, while a vertex of degree three forces at least three. Therefore \(\chi'(G)=3\).
Worked Example: Unequal Parts and Three Matching Classes
Let \(G\) have parts \(X=\{a,b,c,d\}\) and \(Y=\{1,2,3\}\), with \(E=\{a1,a2,a3,b2,b3,c1,c3,d1,d2\}\). Find an optimal coloring.
The degrees in \(X\), found by counting incident edges, are \(3,2,2,2\), respectively. The degrees in \(Y\) are \(\deg(1)=3\), \(\deg(2)=3\), and \(\deg(3)=3\). Hence \(\Delta(G)=3\).
Use these color classes:
| Color | Matching |
|---|---|
| 1 | \(\{a1,b2,c3\}\) |
| 2 | \(\{a2,b3,d1\}\) |
| 3 | \(\{a3,c1,d2\}\) |
In each row, no vertex from \(X\) or \(Y\) appears more than once, so every row is a matching. Reading the rows gives the nine edges \(a1,b2,c3,a2,b3,d1,a3,c1,d2\), each exactly once; this is precisely the specified set \(E\). Thus the three rows give a proper coloring.
Check: There are \(3+3+3=9\) listed edges. The degree sum on \(X\) is \(3+2+2+2=9\), and on \(Y\) it is \(3+3+3=9\). The coloring uses three colors, and the degree-three vertices require at least three, so \(\chi'(G)=3\).
Worked Example: Disconnected Components and an Isolated Vertex
Let \(G\) have parts \(X=\{u,v,w,x,z\}\) and \(Y=\{1,2,3,4\}\), with edge set \(E=\{u1,u2,v1,v2,w3,x3,x4\}\). The vertex \(z\) is isolated. Construct an optimal coloring.
The edges \(u1,u2,v1,v2\) form one component, a 4-cycle. The edges \(w3,x3,x4\) form another component, a path with endpoints \(w\) and \(4\). The isolated vertex \(z\) forms a component with no edges. The degrees are \(\deg(u)=2,\deg(v)=2,\deg(w)=1,\deg(x)=2,\deg(z)=0\); on the other side, \(\deg(1)=2,\deg(2)=2,\deg(3)=2,\deg(4)=1\). Thus \(\Delta(G)=2\).
Take the two classes \(M_1=\{u1,v2,w3,x4\}\) and \(M_2=\{u2,v1,x3\}\). In \(M_1\), the endpoints on the two sides are \(\{u,v,w,x\}\) and \(\{1,2,3,4\}\); in \(M_2\), they are \(\{u,v,x\}\) and \(\{2,1,3\}\). Each class is therefore a matching. The classes are disjoint, and listing them together gives all seven edges of \(E\).
Check: The total degree on \(X\) is \(2+2+1+2+0=7\), and on \(Y\) it is \(2+2+2+1=7\), matching the seven edges. Two colors suffice, and the vertex \(u\), of degree two, requires two distinct colors. Hence \(\chi'(G)=2\). The isolated vertex contributes no incident edge and does not change the coloring.
A Reliable Construction Workflow
For a small explicit bipartite graph, a useful way to organize the work is to start with the vertices of largest degree. Their incident edges must all receive different colors. Then assign remaining edges while maintaining the matching condition in each color class. The Kőnig theorem guarantees that a \(\Delta(G)\)-coloring exists, but it does not make every partial or greedy choice safe. A proposed coloring must be checked against the entire edge set.
Count the incident edges at every vertex and record \(\Delta(G)\). This is a lower bound on the number of colors.
Place edges into \(\Delta(G)\) groups, checking as you go that no group repeats an endpoint.
Compare the union of the groups with the specified edge set: every edge must occur once, and no edge may be omitted or duplicated.
The matching groups give a proper coloring with \(\Delta(G)\) colors, while the degree bound rules out fewer.
This workflow is a certificate-based construction, not a claim that an arbitrary greedy assignment will always succeed. For larger graphs, more systematic methods are needed to find the classes; the certificate checks remain the same.
Common Pitfall: A Color Class Must Be a Matching
Counting the number of edges in each color is not enough to verify a coloring. A class may have few edges and still contain two edges incident to the same vertex. For instance, in the first example, the proposed class \(\{a1,c1\}\) is not a matching: both edges meet at vertex \(1\). Assigning them the same color violates properness, even though there are only two edges in the class. The correction is to put \(a1\) and \(c1\) in different classes, as in the displayed coloring.
There is a second check that is just as important: classes that are individually matchings do not certify a coloring unless they partition all of \(E\). Leaving out one edge means the coloring is incomplete; listing an edge twice does not create a partition. To prove optimality, finish by comparing the number of classes with \(\Delta(G)\), rather than relying only on the fact that the graph is bipartite.
Check Your Understanding
Use the matching-certificate method in each question. State the degree bound and check every proposed color class at its endpoints.
- For the graph with parts \(X=\{p,q\}\), \(Y=\{1,2,3\}\), and edges \(p1,p2,q2,q3\), give a partition into matchings and determine \(\chi'(G)\).
- Explain why any proper edge coloring of a graph with a vertex of degree \(r\) uses at least \(r\) colors.
- Can two edges that share a vertex belong to the same matching? Justify your answer from the definition.
- A proposed coloring has \(\Delta(G)\) color classes, each a matching, but one edge is missing. Why is this not yet an optimality certificate?
- What are \(\chi'(G)\) and \(\Delta(G)\) when \(G\) has vertices but no edges? Explain why isolated vertices do not require colors.