What an Edge-List Check Verifies
A proposed coloring is checked locally: for each edge, compare the colors assigned to its two endpoints. One edge whose endpoints have the same color is enough to show that the assignment is not proper. To verify that it is proper, however, every edge must pass the test. This makes the vertex list, edge list, and color assignment all part of the certificate being checked.
Throughout, graphs are finite and simple: edges are undirected, there are no loops, and there are no multiple edges. Write \(G=(V,E)\), where \(V\) is the vertex set and \(E\) is the set of unordered pairs of distinct vertices. An edge with endpoints \(u\) and \(v\) is written \(uv\). A vertex list must include every vertex, including isolated vertices; an edge list specifies which pairs are edges.
The labels themselves have no special meaning: red and blue could be replaced by \(1\) and \(2\), provided the assignment remains the same up to relabeling. A color assignment must give exactly one label to every vertex in \(V\). A vertex that is missing a label, or is assigned two labels, does not yet have a well-defined color assignment to check.
When a graph is given by lists, first confirm that the data describe the graph being checked. Every listed edge must have both endpoints in the vertex list, and an edge cannot join a vertex to itself in a simple graph. Repeated appearances of the same unordered pair do not create different edges; treat the edge set as a set. If an edge list is claimed to represent a separately specified graph, also verify that no edge has been omitted. Passing a check on an incomplete list verifies only the listed edges, not the intended graph.
The Edge-by-Edge Criterion
Proof. Suppose first that \(c\) is proper. By definition, the endpoints of every edge have different colors, so no edge belongs to \(B\). Hence \(B=\varnothing\). Conversely, suppose \(B=\varnothing\). Take any edge \(uv\in E\). If \(c(u)=c(v)\), then the definition of \(B\) gives \(uv\in B\), contradicting \(B=\varnothing\). Therefore \(c(u)\ne c(v)\) for every edge, which is exactly the definition of a proper coloring. \(\square\)
This gives a direct procedure. Check that the assignment is defined on every vertex. Then examine the edges one at a time, recording the two endpoint colors and whether they differ. If an edge has equal endpoint colors, stop: that edge is a concrete certificate of invalidity. If every edge has been checked and none fails, the theorem proves the assignment is proper. For an edge-free graph, the test passes because there are no edges to violate the condition.
Confirm the vertex set, edge list, and assignment are well formed, and that every edge endpoint is a listed vertex.
For each \(uv\in E\), write \(c(u)\) and \(c(v)\), then test whether they are unequal.
If a comparison fails, name the edge and its common color. Otherwise state that all edges passed, so the assignment is proper.
Worked Checks
Worked Example: Finding a Violating Edge
Let \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,24,34,45\}\). Consider the assignment \(c(1)=\text{red}\), \(c(2)=\text{blue}\), \(c(3)=\text{green}\), \(c(4)=\text{blue}\), and \(c(5)=\text{red}\). Check whether it is proper.
The assignment gives one color to each of the five vertices. Now compare the endpoints of every listed edge.
| Edge | Endpoint colors | Comparison |
|---|---|---|
| \(12\) | red, blue | Different; passes |
| \(13\) | red, green | Different; passes |
| \(24\) | blue, blue | Equal; fails |
| \(34\) | green, blue | Different; passes |
| \(45\) | blue, red | Different; passes |
The edge \(24\) has both endpoints colored blue, so \(24\in B\). The assignment is not proper; no further calculation is needed to establish that conclusion. The other four comparisons do not undo this violation.
Check: the only edge with equal endpoint colors is \(24\), so \(B=\{24\}\ne\varnothing\). This agrees with the criterion.
Worked Example: Verifying a Proper Assignment
Let \(V=\{a,b,c,d,e\}\) and \(E=\{ab,ac,bd,cd\}\). Assign \(a\) and \(d\) the color \(X\), and assign \(b\), \(c\), and \(e\) the color \(Y\). The vertex \(e\) is isolated. Check the assignment.
The assignment is defined on all five vertices. The color classes are \(c^{-1}(X)=\{a,d\}\) and \(c^{-1}(Y)=\{b,c,e\}\); both are nonempty, disjoint, and together contain all vertices. Check the edges in the given edge set:
| Edge | Endpoint colors | Comparison |
|---|---|---|
| \(ab\) | \(X,Y\) | Different; passes |
| \(ac\) | \(X,Y\) | Different; passes |
| \(bd\) | \(Y,X\) | Different; passes |
| \(cd\) | \(Y,X\) | Different; passes |
Every edge has endpoints with different colors, so \(B=\varnothing\) and the assignment is proper. The fact that \(b\) and \(c\) share a color causes no problem: they are not adjacent. Likewise, the isolated vertex \(e\) creates no edge comparison to fail.
Check: there are four edges and all four rows pass. The edge list contains no other pair to check, and the assignment covers the isolated vertex as well as the vertices incident to edges.
Worked Example: Why a Complete Edge List Matters
Let \(V=\{1,2,3,4,5\}\) and let the intended graph have edge set \(E=\{12,23,34,45,15\}\). Suppose a supplied edge list accidentally omits \(15\), leaving \(\{12,23,34,45\}\). Consider \(c(1)=\text{red}\), \(c(2)=\text{blue}\), \(c(3)=\text{red}\), \(c(4)=\text{blue}\), and \(c(5)=\text{red}\).
If only the four supplied edges are checked, the comparisons are \(12\): red versus blue; \(23\): blue versus red; \(34\): red versus blue; and \(45\): blue versus red. Each listed edge passes. That result establishes only that the assignment passes on the supplied list.
For the intended graph, the omitted edge \(15\) must also be checked. Its endpoints both have color red, so \(15\in B\) for the intended edge set. The assignment is not proper for that graph.
Check: on the four-edge list, the violation set is empty. On the intended five-edge set, the violation set is \(B=\{15\}\). The different conclusions come from different edge sets, not from any change in the assignment.
What a Successful Check Does—and Does Not—Show
Proof. A subgraph \(H\) has a vertex set contained in \(V\) and an edge set contained in \(E\), with each edge joining vertices in the subgraph. Restrict \(c\) to the vertices of \(H\). For any edge \(uv\) of \(H\), \(uv\) is also an edge of \(G\). Since \(c\) is proper on \(G\), \(c(u)\ne c(v)\). The restricted assignment therefore gives different colors to the endpoints of every edge of \(H\), so it is proper on \(H\). \(\square\)
The converse does not follow: checking only some edges can miss a violation on an omitted edge, as the preceding example demonstrates. Thus a useful report says which graph and edge set were checked. “All listed edges pass” and “the assignment is proper on the intended graph” are the same conclusion only when the list includes exactly that graph’s edges.
Properness is also different from optimality. A successful edge check proves that the proposed assignment is a proper coloring; it does not prove that the number of colors used is as small as possible. In particular, checking that no edge has equally colored endpoints cannot rule out the existence of a different proper coloring using fewer colors. That is a separate question from verifying the assignment provided.
Common Mistakes
Checking only the first few edges. A coloring that passes several comparisons can still fail on the next edge. In the first example, four edges pass, but \(24\) fails. To certify properness, finish the full edge list.
Rejecting vertices that share a color. The condition concerns adjacent vertices, not every pair of vertices. In the second example, \(b\) and \(c\) both have color \(Y\), but \(bc\notin E\), so their shared color is not a violation.
Confusing a color label with a required nonempty class. A label may be available but unused. If \(C=\{\text{red},\text{blue},\text{green}\}\) and no vertex is green, the green color class is empty; it is not one of the nonempty sets in the partition of \(V\). This does not affect the edge-by-edge test.
Forgetting isolated vertices or omitted edges. An isolated vertex still belongs in the vertex list and must have a color. Conversely, an edge absent from a supplied list cannot be tested from that list. Confirm that the list is complete for the graph whose coloring is being assessed.
Check Your Understanding
For each question, state the vertex set and edge set you are using when relevant, and justify the conclusion by the edge comparisons.
- Let \(V=\{1,2,3,4\}\), \(E=\{12,23,34\}\), and assign colors red, blue, red, blue to \(1,2,3,4\), respectively. Is the assignment proper?
- In a graph with edge \(uv\), suppose \(c(u)=c(v)\). What specific evidence does this provide about the assignment?
- Can two nonadjacent vertices have the same color in a proper coloring? Explain using the definition.
- Why does checking an incomplete edge list fail to certify properness on the intended graph?
- If a color label has no vertices assigned to it, does that alone make the coloring improper? Explain the role of nonempty color classes.