Edge Chromatic Number and the Maximum-Degree Bound

Edge Colors and the Number of Colors Required

A proper vertex coloring assigns different colors to adjacent vertices. For edge coloring, the objects receiving colors are the edges: edges that share an endpoint must receive different colors. This local requirement immediately creates a lower bound. If a vertex is incident to many edges, all those edges must have different colors. The largest degree in the graph therefore gives a necessary minimum number of colors.

Throughout, graphs are finite and simple. A proper edge coloring is an assignment of colors to the edges such that any two distinct edges with a common endpoint receive different colors. A palette of $k$ colors means a set of $k$ available colors; a coloring need not use every color in its palette.

Definition: The edge chromatic number $\chi'(G)$ is the minimum number of colors in a proper edge coloring of $G$. If $G$ has no edges, define $\chi'(G)=0$. For a graph with no vertices, take $\Delta(G)=0$; for any edgeless graph, every vertex has degree zero, so its maximum degree is also zero.

This minimum exists: if $G$ has $m$ edges, assigning a different color to each edge gives a proper edge coloring using $m$ colors. When $m=0$, the empty assignment uses zero colors. Thus there is at least one feasible number of colors, and the least such nonnegative integer is well-defined.

Color Classes and Matchings

A matching is a set of edges no two of which share an endpoint. Edge coloring can be understood by grouping edges according to their colors: each group must be a matching. This observation links the definition to the matching color classes considered in proper edge coloring.

Lemma: In a proper edge coloring, the edges of each one color form a matching. Conversely, if the edge set is partitioned into matchings, assigning a different color to each matching gives a proper edge coloring.

Proof. Fix a color in a proper edge coloring. If two edges of that color shared an endpoint, the coloring would violate the requirement that incident edges have different colors. Thus its color class is a matching. Conversely, suppose the edge set is partitioned into matchings and give each matching its own color. Two edges with the same color belong to one matching and therefore have no common endpoint. Hence every pair of incident edges has different colors, as required. $\square$

The lemma describes the constraint imposed by a color: its edges cannot meet. It does not say that the edges in different color classes must meet, nor that every matching in a partition has the same size. The maximum-degree bound follows by examining just one vertex and the edges incident to it.

The Maximum-Degree Bound

Theorem: For every finite simple graph $G$, $$ \chi'(G)\ge \Delta(G). $$

Proof. If $\Delta(G)=0$, then $G$ has no edges: any edge would give each of its endpoints degree at least $1$. Hence $\chi'(G)=0=\Delta(G)$, including when $G$ has no vertices. Now suppose $\Delta(G)>0$. Since $G$ is finite, some vertex $v$ has degree $\deg(v)=\Delta(G)$. Consider any proper edge coloring of $G$ using $k$ colors. The $\Delta(G)$ distinct edges incident to $v$ must all receive different colors, because each pair shares endpoint $v$. Therefore the palette contains at least $\Delta(G)$ colors, so $k\ge\Delta(G)$. This holds for every proper edge coloring; in particular, it holds for one using the minimum number $\chi'(G)$ of colors. Thus $\chi'(G)\ge\Delta(G)$. $\square$

The proof uses only edges at a single vertex of maximum degree. It gives a necessary condition for a coloring, not a general method for constructing a coloring with exactly $\Delta(G)$ colors. Even after the incident edges at a vertex have distinct colors, other edges elsewhere in the graph may impose further constraints.

Worked Example: A Star Forces Four Colors

Let $G=(V,E)$ have $V=\{c,1,2,3,4\}$ and $E=\{c1,c2,c3,c4\}$. The center $c$ has degree $4$, and each of $1,2,3,4$ has degree $1$. Thus the degrees are $4,1,1,1,1$, so $\Delta(G)=4$. The theorem gives $\chi'(G)\ge 4$.

Assign four colors as follows: give $c1$ red, $c2$ blue, $c3$ green, and $c4$ yellow. Every two distinct edges share $c$, and this assignment gives them different colors. Therefore it is a proper coloring with four colors, so $\chi'(G)\le4$. Combining the two inequalities gives $\chi'(G)=4$.

Check: the four edges incident to $c$ use red, blue, green, and yellow once each, so the lower bound is attained. Also, the edge count is $4$, matching the four listed edges; the degree sum is $4+1+1+1+1=8=2\cdot4$.

Worked Example: A Bound Attained with Three Colors

Let $G=(V,E)$ have $V=\{1,2,3,4\}$ and $E=\{12,23,31,14\}$. The degrees are $\deg(1)=3$, $\deg(2)=2$, $\deg(3)=2$, and $\deg(4)=1$, so $\Delta(G)=3$. Consequently $\chi'(G)\ge3$.

Use red on $12$, blue on $13$, and green on both $23$ and $14$. The two green edges $23$ and $14$ are disjoint: their endpoint sets $\{2,3\}$ and $\{1,4\}$ have no common vertex. At vertex $1$, the incident edges $12,13,14$ have colors red, blue, and green. At vertex $2$, edges $12,23$ have colors red and green; at vertex $3$, edges $13,23$ have colors blue and green. Vertex $4$ has only one incident edge. Thus no two incident edges have the same color, and the coloring is proper.

We have exhibited a three-coloring, so $\chi'(G)\le3$; together with $\chi'(G)\ge3$, this gives $\chi'(G)=3$. Check: the four listed edges have degrees summing to $3+2+2+1=8$, which equals $2|E|=2\cdot4$. The coloring uses three colors, and the three edges at vertex $1$ require three distinct colors.

Worked Example: Several Vertices Attain the Maximum Degree

Let $G=(V,E)$ have $V=\{a,b,c,d,e,f,g\}$ and $E=\{ab,ac,ad,bc,be,cf,de\}$. From this edge list, the degrees are $\deg(a)=3$ from $ab,ac,ad$, $\deg(b)=3$ from $ab,bc,be$, $\deg(c)=3$ from $ac,bc,cf$, $\deg(d)=2$ from $ad,de$, $\deg(e)=2$ from $be,de$, $\deg(f)=1$ from $cf$, and $\deg(g)=0$. Hence $\Delta(G)=3$, attained at $a,b,c$, and $\chi'(G)\ge3$.

For an upper bound, color $ab$ red, $ac$ blue, $ad$ green, $bc$ green, $be$ blue, $cf$ red, and $de$ red. At $a$, the incident colors are red, blue, and green; at $b$, they are red, green, and blue; at $c$, they are blue, green, and red. At $d$, the colors are green and red; at $e$, they are blue and red; at $f$, only red appears; and $g$ has no incident edge. Each vertex therefore has distinct colors on all its incident edges, so the coloring is proper. It uses three colors, giving $\chi'(G)\le3$, and thus $\chi'(G)=3$.

Check: the edge list has seven edges. The degree sum is $3+3+3+2+2+1+0=14$, which equals $2\cdot7$. The isolated vertex $g$ creates no additional coloring constraint, while each of $a,b,c$ requires at least three colors.

What the Bound Does—and Does Not—Say

The theorem is useful because it can rule out too few colors without requiring a search over all possible edge colorings. If a graph has a vertex of degree $r$, then any palette of fewer than $r$ colors is impossible. In particular, inspecting a vertex of maximum degree gives the strongest lower bound available from this argument.

The bound is not itself a coloring algorithm. To prove an upper bound $\chi'(G)\le k$, one must exhibit a proper edge coloring with $k$ colors or give another justified construction. The examples above establish equality by doing both jobs: they first obtain the lower bound from degrees and then verify a coloring using exactly that many colors.

Common pitfall: counting edges instead of incident edges. In the graph with $V=\{1,2,3,4\}$ and $E=\{12,23,31,14\}$, there are four edges. A mistaken argument might say that all four need different colors and conclude $\chi'(G)\ge4$. That condition is not part of proper edge coloring: only edges sharing an endpoint must differ. In particular, $23$ and $14$ are disjoint, so they can share green. The verified coloring uses three colors, and the degree calculation gives the correct lower bound $\Delta(G)=3$.

When using the theorem, first compute degrees from the edge set, then take their maximum. Do not confuse the maximum degree with the size of the graph, which is its total number of edges. Finally, keep the direction of the inequality in view: a lower bound says that fewer colors cannot work; it does not promise that the bound itself can always be attained.

Check Your Understanding

For each question, distinguish the degree-based lower bound from any coloring you may use to establish an upper bound.

Why must all edges incident to one vertex have distinct colors in a proper edge coloring?
A graph has maximum degree $5$. What lower bound does the theorem give for its edge chromatic number, and what does that bound not establish?
Explain why each color class in a proper edge coloring is a matching.
For $V=\{u,v,w,x\}$ and $E=\{uv,uw,ux,vw\}$, calculate every vertex degree and the resulting lower bound for $\chi'(G)$.
Can two disjoint edges receive the same color in a proper edge coloring? State the condition that determines whether two edges must have different colors.

Edge Chromatic Number and the Maximum-Degree Bound

What You'll Learn