Classifying Edge Chromatic Numbers by Worked Examples

A Practical Framework for Determining \(\chi'(G)\)

To determine the edge chromatic number of a particular graph, one needs both a lower bound and a coloring that attains it. A proper edge coloring assigns colors to edges so that any two edges sharing a vertex receive different colors. The edge chromatic number \(\chi'(G)\) is the least number of colors in such a coloring. In this tutorial, graphs are finite and simple unless stated otherwise.

Two standard results guide the classification. First, every simple graph with at least one edge satisfies \(\Delta(G)\leq\chi'(G)\leq\Delta(G)+1\), by Vizing’s theorem, proved in the earlier material on Vizing’s theorem. Second, Kőnig’s line coloring theorem says that every bipartite graph satisfies \(\chi'(G)=\Delta(G)\); the earlier material on bipartite edge coloring establishes this result. These results usually narrow the answer to two possibilities. To decide between them, we can use a bipartition, construct color classes explicitly, or obtain a stronger lower bound by considering how many edges can share one color.

Proof. A matching is a set of pairwise nonadjacent edges. If two edges of the same color shared an endpoint, the coloring would not be proper. Therefore every color class is a matching. \(\square\)

This observation gives the basic degree lower bound. At a vertex of degree \(\Delta(G)\), all incident edges need different colors. A matching-based count can sometimes give more: if every matching in a graph has at most \(q\) edges and \(G\) has \(m\) edges, then \(k\) colors cover at most \(kq\) edges. Thus \(m\leq kq\), so \(k\geq\lceil m/q\rceil\). We will use this count for one explicit graph, without needing a general classification criterion.

Worked Classifications

The \(K_5\) calculation illustrates an important distinction: a lower-bound argument may determine the exact number without itself constructing a coloring. The upper bound is a separate obligation. Here it is supplied by Vizing’s theorem, whose hypotheses apply because \(K_5\) is simple. The attempted lists above also show why a purported coloring must be checked edge by edge: a missing edge or a repeated endpoint invalidates it.

Two Useful General Checks

Proof. Choose a vertex \(v\) with degree \(\Delta(G)\). Every pair of distinct edges incident with \(v\) must receive different colors in a proper edge coloring. Thus the \(\Delta(G)\) edges incident with \(v\) require at least \(\Delta(G)\) colors. Since this holds for every proper edge coloring, the minimum number of colors satisfies \(\chi'(G)\geq\Delta(G)\). \(\square\)

Proof. In any proper edge coloring with \(k\) colors, each color class is a matching and therefore contains at most \(q\) edges. The \(k\) color classes together contain all \(m\) edges, so \(m\leq kq\). Dividing by the positive integer \(q\) gives \(k\geq m/q\). Since \(k\) is an integer, \(k\geq\lceil m/q\rceil\). This holds for every proper edge coloring, including one using the minimum number \(\chi'(G)\) of colors, and proves the claim. \(\square\)

Disconnected graphs require no new coloring principle, but their components should all be checked. If \(G\) has components \(G_1,\ldots,G_r\), then its edge chromatic number is the maximum of the components’ edge chromatic numbers. The reason is that edges in different components have no shared endpoints, so colors can be reused across components.

Proof. Let \(k=\chi'(G)\). Restricting a proper coloring of \(G\) to any component \(G_i\) gives a proper coloring of \(G_i\), so \(\chi'(G_i)\leq k\) for every \(i\). Hence \(\max_i\chi'(G_i)\leq\chi'(G)\). Conversely, let \(K=\max_i\chi'(G_i)\). Color each component using at most \(K\) colors, reusing the same set of \(K\) colors in every component. There are no edges between distinct components, so edges in different components cannot conflict at a vertex. This produces a proper coloring of \(G\) using at most \(K\) colors, giving \(\chi'(G)\leq K\). If \(G\) has no edges, the empty assignment uses zero colors, and no negative number of colors is possible; thus \(\chi'(G)=0\). \(\square\)

How to Combine the Bounds

For a concrete simple graph with at least one edge, begin by calculating \(\Delta(G)\). The degree argument gives the lower bound \(\chi'(G)\geq\Delta(G)\), while Vizing’s theorem gives \(\chi'(G)\leq\Delta(G)+1\). If the graph is bipartite, Kőnig’s line coloring theorem settles the question at \(\Delta(G)\). Otherwise, look for an explicit coloring with \(\Delta(G)\) colors, or strengthen the lower bound using a matching count. A coloring with \(\Delta(G)+1\) colors can establish the upper bound, but by itself does not rule out a coloring with fewer colors.

In particular, “Vizing gives at most \(\Delta+1\)” is not a classification: it leaves open whether the graph is class 1 or class 2. A complete classification needs matching lower and upper bounds. For class 1, a \(\Delta\)-edge-coloring together with the degree lower bound suffices. For class 2, a lower bound of \(\Delta+1\), together with Vizing’s upper bound, suffices.

Common Pitfall

Do not infer class 2 merely from the failure of a coloring you tried. In \(K_4\), one might calculate \(\Delta(K_4)=3\) and incorrectly conclude that \(\chi'(K_4)=4\), on the mistaken assumption that a nonbipartite graph must need the extra color. But the three matching classes \(\{12,34\}\), \(\{13,24\}\), and \(\{14,23\}\) give a proper 3-edge-coloring. Together with the lower bound \(\chi'(K_4)\geq3\), this proves \(\chi'(K_4)=3\). Nonbipartiteness alone does not decide between class 1 and class 2; use a valid lower bound and verify an upper-bound coloring or theorem.