Coloring Edges Without Conflicts
In a proper vertex coloring, the objects receiving colors are vertices. In an edge coloring, the objects receiving colors are edges, and the restriction is local: edges that meet at a vertex must have different colors. This condition is useful whenever edges represent activities, connections or tasks that cannot share an endpoint and therefore cannot be assigned the same label.
Throughout, graphs are finite and simple. Two distinct edges are adjacent if they share an endpoint. A matching is a set of edges no two of which are adjacent. A maximum matching has the largest possible number of edges among all matchings in the graph; a maximal matching is one to which no edge can be added while retaining a matching. A perfect matching is a matching incident with every vertex. These are different properties: being a color class requires only being a matching.
The definition imposes no requirement that every available color be used. If \(E\) is empty, the function from \(E\) to \(C\) is empty and is proper, including when \(V\) contains isolated vertices. If \(E\) is nonempty, a coloring requires at least one available color. A color class can also be empty; the empty set is a matching.
A Local Test and the Matching Connection
Proof. Assume first that the coloring is proper. Any two distinct edges incident with the same vertex share that endpoint, so they are adjacent. The definition of properness therefore gives them different colors. Conversely, assume that all edges incident with each vertex have different colors. If two distinct edges are adjacent, they share some vertex \(v\), so they are among the edges incident with \(v\). By the assumption, they have different colors. Thus every pair of adjacent edges has different colors, which is exactly properness. At an isolated vertex or a vertex incident with one edge, the condition has no pair to check and is satisfied. \(\square\)
This proposition gives a direct way to check a proposed coloring: inspect the edges around each vertex. There is no need to compare edges that do not meet. The same condition explains why color classes are matchings.
Proof. Suppose first that the coloring is proper. Fix a color \(i\in C\). If two distinct edges in \(E_i\) shared an endpoint, they would be adjacent and would have the same color \(i\), contrary to properness. Hence no two edges of \(E_i\) are adjacent, so \(E_i\) is a matching. This applies to every color, including unused colors, whose classes are empty matchings.
Conversely, suppose that every color class is a matching. Take any two distinct adjacent edges \(e\) and \(f\). If they had the same color \(i\), then both would belong to \(E_i\), contradicting the assumption that \(E_i\) is a matching. Therefore adjacent edges have different colors, and the coloring is proper. If \(E\) is empty, there are no adjacent edges to consider and every color class is empty, so both statements hold. \(\square\)
Equivalently, a proper edge coloring divides the edge set into disjoint matchings: the color classes are disjoint because each edge receives exactly one color, and their union is \(E\). In the other direction, any partition of \(E\) into matchings defines a proper edge coloring by assigning one distinct color to each part. This correspondence concerns the structure of the color classes; it does not say that the classes have equal sizes, are maximum matchings, or cover every vertex.
Checking Explicit Colorings
Worked Example: Coloring the Edges of a Star
Let \(G=(V,E)\) have \(V=\{a,b,c,d\}\) and \(E=\{ab,ac,ad\}\). Assign the colors red to \(ab\), blue to \(ac\), and green to \(ad\). Check whether this is a proper edge coloring.
At \(a\), the three incident edges are \(ab,ac,ad\), with colors red, blue and green, respectively; these are pairwise different. At \(b\), the only incident edge is \(ab\). At \(c\), the only incident edge is \(ac\). At \(d\), the only incident edge is \(ad\). Thus every vertex satisfies the local test.
The color classes are \(E_{\text{red}}=\{ab\}\), \(E_{\text{blue}}=\{ac\}\) and \(E_{\text{green}}=\{ad\}\). Each singleton is a matching, so the theorem gives a second check that the coloring is proper. The number of edges is \(3\), and the three displayed singleton classes contain \(1+1+1=3\) edges in total, with no edge omitted or repeated.
Check: the only pairs of distinct edges are \(ab,ac\), \(ab,ad\), and \(ac,ad\); each pair meets at \(a\) and receives different colors. The coloring is proper. None of its color classes is a perfect matching, since each contains only one edge and leaves other vertices uncovered.
Worked Example: Building a Coloring from Matchings
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,23,34,45\}\). Consider the three sets \(M_1=\{12,34\}\), \(M_2=\{13,45\}\), and \(M_3=\{23\}\). Use these sets as color classes and test the resulting coloring.
First check that each set is a matching. In \(M_1\), the endpoints of \(12\) are \(1,2\), and the endpoints of \(34\) are \(3,4\), so the two edges share no endpoint. In \(M_2\), the endpoints of \(13\) are \(1,3\), and those of \(45\) are \(4,5\), so these edges are disjoint as well. The singleton \(M_3\) is a matching. The sets are pairwise disjoint and their union is \(\{12,13,23,34,45\}=E\), so they form a partition of the edge set.
Assign red to \(M_1\), blue to \(M_2\), and green to \(M_3\). To check directly, vertex \(1\) is incident with \(12\) (red) and \(13\) (blue); vertex \(2\) is incident with \(12\) (red) and \(23\) (green); vertex \(3\) is incident with \(13\) (blue), \(23\) (green), and \(34\) (red); vertex \(4\) is incident with \(34\) (red) and \(45\) (blue); and vertex \(5\) is incident only with \(45\) (blue). No vertex has two incident edges of the same color.
Check: the three color classes have sizes \(2,2,1\), and \(2+2+1=5=|E|\). Each edge in the stated edge set appears in exactly one class, and all classes are matchings. By the theorem, the coloring is proper.
Worked Example: Finding and Repairing a Conflict
Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,31,34\}\). Suppose the proposed coloring assigns red to \(12\) and \(23\), and blue to \(31\) and \(34\). Determine whether it is proper, and if not, give a repair.
At vertex \(2\), both incident edges \(12\) and \(23\) are red. Since they are distinct adjacent edges with equal colors, the proposed coloring is not proper. In matching language, the red class \(\{12,23\}\) is not a matching because its two edges share vertex \(2\). There is also a conflict at vertex \(3\): the blue edges \(31\) and \(34\) share vertex \(3\), so the blue class is not a matching either.
One repair is to assign red to \(12\) and \(34\), blue to \(23\), and green to \(31\). The repaired red edges have endpoint sets \(\{1,2\}\) and \(\{3,4\}\), which are disjoint. The blue and green classes each contain a single edge. Thus all three classes are matchings.
Checking at the vertices confirms the repair: vertex \(1\) sees red \(12\) and green \(31\); vertex \(2\) sees red \(12\) and blue \(23\); vertex \(3\) sees blue \(23\), green \(31\), and red \(34\); vertex \(4\) sees only red \(34\). Each vertex has distinct colors on its incident edges.
Check: the repaired classes contain \(2+1+1=4\) edges, and their union is \(\{12,23,31,34\}=E\). The repaired coloring is proper; the original one is not.
What the Matching Viewpoint Does—and Does Not—Say
The matching description changes the way a coloring can be designed or verified. Instead of checking all pairs of edges in the graph, one can group edges by color and check whether any group contains two edges with a common endpoint. Conversely, one can start by finding several matchings that partition the edges and then use them as color classes. Either method is justified by the theorem.
It is important not to infer extra properties from the word “matching.” A color class need not be maximum: it might be possible to find a larger matching elsewhere in the graph. It need not be maximal: an edge of another color might be added to it without creating a shared endpoint. And it need not be perfect: vertices may be left uncovered. Properness requires only that no two edges of one color meet.
A common mistake is to check only that the coloring uses different colors on edges with different names, or to compare only some of the incident edges. For example, in the uncorrected coloring of the last example, one might observe that \(12\) and \(34\) have different colors and conclude that the coloring has no conflict. But that pair does not share an endpoint, so it is irrelevant to properness. The actual test at vertex \(2\) compares \(12\) and \(23\), both red; this is a concrete violation. The correction is to check every pair of edges incident with each vertex, or equivalently to test each color class for shared endpoints.
The color-class viewpoint is a structural characterization, not a claim about how many colors are needed. The number of colors in a particular coloring is simply the number of colors it uses; determining the smallest possible number is a separate optimization question. Here the essential fact is the exact equivalence: the edges of any one color form a matching, and a partition into matchings gives a proper edge coloring.
Check Your Understanding
Use the local test or the matching characterization to answer each question.
- For \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\), assign red to \(12\) and \(34\), and blue to \(23\). Is the coloring proper? State the color classes.
- Explain why two edges in the same color class cannot share an endpoint in a proper edge coloring.
- Suppose \(E\) is partitioned into three matchings. Describe how to turn that partition into a proper edge coloring.
- Can an empty color class occur in a proper edge coloring? Explain using the definition.
- Give an example of a matching that is not perfect, and explain why it can still be a color class.