Why Edge Counts Can Force an Extra Color
In a proper edge coloring, edges of the same color cannot share an endpoint. Thus each color class is a matching, and a matching can cover at most half the vertices of any subgraph. If a subgraph has more edges than this matching bound permits across \(\Delta(G)\) colors, then the whole graph cannot be colored with \(\Delta(G)\) colors. This gives a direct certificate for a class two graph, without needing to construct an edge coloring.
Throughout, graphs are finite and simple. An edge coloring assigns a color to each edge so that any two edges sharing a vertex receive different colors. The edge chromatic number \(\chi'(G)\) is the minimum number of colors in such a coloring. The maximum degree of \(G\) is \(\Delta(G)\). A graph is class one if \(\chi'(G)=\Delta(G)\), and class two if \(\chi'(G)=\Delta(G)+1\). Vizing’s theorem, proved earlier in the edge-coloring material, states that every finite simple graph satisfies \(\Delta(G)\leq\chi'(G)\leq\Delta(G)+1\).
The strict inequality matters. It says there are more edges in \(H\) than \(\Delta(G)\) matchings on \(V(H)\) could contain. The definition also covers subgraphs with isolated vertices: those vertices count in \(|V(H)|\), but do not increase the number of edges a matching can have beyond \(\lfloor |V(H)|/2\rfloor\).
The Matching Bound and the Certificate
Proof. Each edge of \(M\) has two endpoints, and distinct edges of a matching have no common endpoint. Thus the \(2|M|\) endpoints are distinct members of the set of \(h\) vertices. Therefore \(2|M|\leq h\). Since \(|M|\) is an integer, \(|M|\leq\lfloor h/2\rfloor\). This also covers \(h=0\) or \(h=1\): in either case the matching has no edges and the bound is zero. \(\square\)
Proof. Write \(h=|V(H)|\) and \(\Delta=\Delta(G)\). Suppose first that \(G\) has a proper edge coloring with at most \(\Delta\) colors. For any one color, the edges of that color which lie in \(H\) form a matching on \(V(H)\): no two such edges share an endpoint, because the coloring is proper in \(G\). By the Lemma, this color occurs on at most \(\lfloor h/2\rfloor\) edges of \(H\). Summing over at most \(\Delta\) colors gives \[ |E(H)|\leq\Delta\lfloor h/2\rfloor, \] contrary to the hypothesis. Hence \(\chi'(G)>\Delta(G)\). Vizing’s theorem applies because \(G\) is finite and simple, and gives \(\chi'(G)\leq\Delta(G)+1\). Since \(\chi'(G)\) is an integer, \(\chi'(G)=\Delta(G)+1\), so \(G\) is class two. If \(\Delta(G)=0\), the hypothesis cannot hold: a graph of maximum degree zero has no edges, and the right side is zero. Thus the implication has no exceptional case at \(\Delta(G)=0\). \(\square\)
The counting step is the essential obstruction: each color can contribute at most \(\lfloor h/2\rfloor\) edges inside \(H\). The theorem is a sufficient test, not an equivalence. If no subgraph satisfies the strict inequality, this argument gives no conclusion about whether \(G\) is class one or class two.
Worked Example: The 5-Cycle
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,34,45,51\}\). This is the cycle \(C_5\). Each vertex has degree \(2\), so \(\Delta(G)=2\). Take \(H=G\). It has five vertices and five edges, and the criterion’s threshold is \[ \Delta(G)\lfloor |V(H)|/2\rfloor=2\lfloor 5/2\rfloor=2\cdot2=4. \] Since \(5>4\), \(H\) is overfull with respect to \(G\), so the theorem gives \(\chi'(G)=3\).
For a direct coloring check, color \(12,34\) with color A; color \(23,45\) with color B; and color \(51\) with color C. Each pair assigned the same color has disjoint endpoints, so this is a proper coloring with three colors. The certificate rules out two or fewer, and this coloring proves that three suffice.
Check: the five listed edges are distinct, and the degrees are \(2,2,2,2,2\), whose sum is \(10\); dividing by \(2\) gives \(5\) edges. The matching bound gives at most \(\lfloor5/2\rfloor=2\) edges per color, so two colors can cover at most \(2\cdot2=4\) edges, not all five.
Worked Example: A Complete Graph of Odd Order
Let \(G=K_5\), with \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,13,14,15,23,24,25,34,35,45\}\). Each vertex is adjacent to the other four, so \(\Delta(G)=4\). Use \(H=G\). Its edge count is \(10\), while the threshold is \[ 4\lfloor 5/2\rfloor=4\cdot2=8. \] Thus \(10>8\), and the criterion proves that \(K_5\) is class two. Vizing’s theorem then gives \(\chi'(K_5)=4+1=5\).
There is also a direct counting check of the obstruction: in any one color, at most two edges can be pairwise disjoint on five vertices. Four colors therefore cover at most \(4\cdot2=8\) edges of \(K_5\), fewer than the ten edges present. The edge count can be verified independently from the degrees: all five degrees equal \(4\), so their sum is \(5\cdot4=20\), and the number of edges is \(20/2=10\).
Worked Example: A Proper Overfull Subgraph in a Connected Graph
Define \(G\) by \(V(G)=\{1,2,3,4,5,6\}\) and \[ E(G)=\{13,14,15,16,23,24,25,34,35,45\}. \] Let \(H\) be the subgraph on \(\{1,2,3,4,5\}\) with \[ E(H)=\{13,14,15,23,24,25,34,35,45\}. \] Thus \(H\) is \(K_5\) with edge \(12\) deleted, and \(G\) is obtained by adding edge \(16\). The graph \(G\) is connected because vertex \(6\) is joined to vertex \(1\), and every other vertex is joined to \(1\) or \(2\).
In \(G\), vertices \(1,2,3,4,5,6\) have degrees \(4,3,4,4,4,1\), respectively. Hence \(\Delta(G)=4\). The subgraph \(H\) has nine edges and five vertices, so its threshold, computed using the ambient degree, is \[ \Delta(G)\lfloor |V(H)|/2\rfloor=4\lfloor5/2\rfloor=4\cdot2=8. \] Because \(9>8\), \(H\) certifies that \(G\) is class two, and Vizing’s theorem gives \(\chi'(G)=5\).
Check: the displayed list for \(H\) has eight edges among the four vertices \(1,2,3,4\) and one more edge \(45\), for nine total; equivalently, its degrees are \(3,3,4,4,4\), summing to \(18\), so it has \(18/2=9\) edges. The full graph has these nine edges and the one additional edge \(16\), so its size is \(10\). Importantly, the criterion uses \(\Delta(G)=4\), not a degree recalculated from an unrelated graph.
What the Strict Inequality Does—and Does Not—Say
For an odd-order \(\Delta\)-regular graph, the whole graph is always overfull when \(\Delta>0\). Indeed, if \(n=|V(G)|\) is odd, then \(n=2k+1\) for some integer \(k\geq0\). The sum of the degrees is \(\Delta n\), and each edge contributes two to this sum, so \(|E(G)|=\Delta(2k+1)/2\). The threshold is \(\Delta\lfloor n/2\rfloor=\Delta k\). Their difference is \(\Delta/2>0\). Since the edge count is an integer, this calculation gives the required strict inequality. The criterion therefore proves that every odd-order regular simple graph of positive degree is class two.
A common mistake is to replace \(>\) by \(\geq\). Equality only says that the matching bound is attained in the count; it does not itself force an extra color.
Worked Example: Equality Is Not an Overfull Certificate
Let \(G=K_{3,3}\), with parts \(X=\{a,b,c\}\) and \(Y=\{x,y,z\}\), and with all nine edges \[ E(G)=\{ax,ay,az,bx,by,bz,cx,cy,cz\}. \] There are six vertices, each of degree \(3\), so \(\Delta(G)=3\). The threshold for \(H=G\) is \(3\lfloor6/2\rfloor=3\cdot3=9\), exactly equal to \(|E(G)|=9\). The strict criterion does not apply.
In this case, a proper three-coloring can be checked directly. Give color A to \(ax,by,cz\), color B to \(ay,bz,cx\), and color C to \(az,bx,cy\). Each color class uses every vertex exactly once, so each is a matching. The three lists are disjoint and together contain all nine edges, verifying the coloring. Since a vertex of degree \(3\) requires at least three colors, \(\chi'(G)=3=\Delta(G)\), so \(G\) is class one.
Check: the nine edges are all possible pairs with one endpoint in \(X\) and one in \(Y\), giving \(3\cdot3=9\). Each of the three color lists has three edges, and every edge occurs once. Equality in the count is therefore consistent with class one.
Another error is to use \(\Delta(H)\) in place of \(\Delta(G)\). The color count being tested is the number of colors available for the ambient graph, so the relevant maximum is \(\Delta(G)\). The proper-subgraph example illustrates why it is important to identify the ambient graph before substituting into the criterion.
Overfull subgraphs are useful because they provide a short lower-bound argument: they show that \(\chi'(G)\) exceeds \(\Delta(G)\), and Vizing’s theorem converts that into the exact value \(\Delta(G)+1\). They do not provide a general test for class one graphs, nor do they require that \(H\) be induced. Any subgraph with the stated edge count is enough.
Check Your Understanding
For each question, keep the ambient graph’s maximum degree separate from the subgraph’s vertex and edge counts.
- Suppose \(H\subseteq G\), \(\Delta(G)=5\), and \(|V(H)|=7\). What is the largest number of edges \(H\) could contain without satisfying the overfull criterion?
- Explain why the edges of one color in a proper edge coloring of \(G\), restricted to \(H\), form a matching.
- For a \(7\)-vertex \(4\)-regular simple graph, compute \(|E(G)|\) and the overfull threshold, and determine whether the criterion applies.
- Why does the criterion give no conclusion for \(K_{3,3}\), even though its edge count equals the threshold?
- Can an overfull subgraph \(H\) be non-induced? State what the criterion then implies about \(G\).