Common Errors in Vertex-Coloring Arguments

Three Checks for a Coloring Argument

A proper coloring is a way to assign colors so that adjacent vertices receive different colors. But a valid coloring does not automatically use the fewest possible colors, a large clique does not necessarily determine the chromatic number, and a familiar theorem cannot be applied without its hypotheses. These distinctions are especially important when an argument uses greedy coloring, clique size, or Brooks' theorem.

All graphs in this tutorial are finite and simple. A proper \(k\)-coloring of \(G=(V,E)\) assigns one of \(k\) colors to each vertex so that the endpoints of every edge have different colors. The chromatic number \(\chi(G)\) is the smallest number of colors in a proper coloring. A clique is a set of pairwise adjacent vertices, and the clique number \(\omega(G)\) is the size of a largest clique. The maximum degree \(\Delta(G)\) is the largest vertex degree.

A correct coloring proves an upper bound: if it uses \(k\) colors, then \(\chi(G)\le k\). To prove that \(k\) is optimal, an argument also needs a lower bound of at least \(k\), or another proof that no coloring with fewer colors exists. The common checks are: verify that the proposed coloring is proper, identify what it proves, and separately justify any claimed lower bound.

Greedy Does Not Mean Optimal

The example illustrates why the vertex order matters: first-fit only avoids colors already used by earlier neighbors. It makes no promise that the colors it has used will be necessary in an optimal coloring. A coloring produced by a greedy algorithm is still useful, since its color count is an upper bound; it simply cannot serve as an optimality proof by itself.

Proof. Consider any vertex order and any vertex \(v\) when it is colored. At most \(\deg(v)\) neighbors of \(v\) have already been colored, so at most \(\deg(v)\) colors are forbidden by those neighbors. Since \(\deg(v)\le\Delta(G)\), at most \(\Delta(G)\) colors are forbidden. Among the \(\Delta(G)+1\) colors \(1,2,\dots,\Delta(G)+1\), at least one is therefore available, and first-fit chooses one of the available colors. This holds for every vertex in the order, so the entire coloring uses at most \(\Delta(G)+1\) colors. If \(G\) has no vertices, it uses no colors and the assertion holds with \(\Delta(G)=0\) under the convention for the empty graph. \(\square\)

This is an upper bound, not a claim that every graph needs \(\Delta(G)+1\) colors. In the path example, \(\Delta(G)=2\), so the bound is 3; the optimal coloring uses only 2.

A Clique Gives a Lower Bound, Not Necessarily the Answer

Proof. Let \(C\) be a clique of size \(\omega(G)\). Every two distinct vertices of \(C\) are adjacent. In a proper coloring, adjacent vertices must have different colors, so the \(\omega(G)\) vertices of \(C\) must receive \(\omega(G)\) distinct colors. Hence every proper coloring of \(G\) uses at least \(\omega(G)\) colors, which gives \(\omega(G)\le\chi(G)\). \(\square\)

This inequality supplies a lower bound. It does not say that every graph has a coloring using exactly \(\omega(G)\) colors. To conclude equality, one must also give a proper coloring with \(\omega(G)\) colors, or otherwise establish the matching upper bound.

A useful exactness certificate combines the two directions of information. If a graph has a proper \(k\)-coloring and contains a clique of size \(k\), then \(\chi(G)=k\): the coloring proves \(\chi(G)\le k\), and the clique proves \(\chi(G)\ge k\). Both are needed. The clique alone cannot prove an upper bound, and a coloring alone cannot prove a lower bound.

Use Brooks' Theorem Only After Checking Its Hypotheses

Connectedness, completeness, and being an odd cycle are not optional details. First check that the graph is connected. Then check whether it is complete or an odd cycle. Only if it passes all these checks does the stated \(\Delta(G)\) bound apply. For a disconnected graph, apply the theorem to its connected components that meet the hypotheses; do not silently treat the whole graph as connected. The general bound \(\chi(G)\le\Delta(G)+1\) remains available without Brooks' theorem.

Odd cycles are the other exception. For example, in \(C_5\) the maximum degree is 2 but the chromatic number is 3, as the preceding example computed. Thus the proposed Brooks conclusion \(\chi(C_5)\le2\) is false. The example is not a counterexample to Brooks' theorem: \(C_5\) is an odd cycle, which the theorem excludes.

For a graph with several components, a safe argument handles each component explicitly. If a component is complete or an odd cycle, use its actual coloring or another applicable result rather than Brooks' theorem on that component. If a component is connected and neither complete nor an odd cycle, Brooks' theorem gives the stated bound for that component. In particular, never infer that the theorem applies to a disconnected graph merely because some of its components satisfy the hypotheses.

A Practical Audit for Coloring Claims

When checking a proof about \(\chi(G)\), separate the claim into the bound it needs and the evidence offered for that bound.

• “This coloring proves \(\chi(G)=k\).” Verify every edge has differently colored endpoints. That establishes only \(\chi(G)\le k\); find a lower bound of \(k\) as well.
• “The clique number is \(k\), so the chromatic number is \(k\).” Clique size proves \(\chi(G)\ge k\). Equality still needs a proper \(k\)-coloring.
• “Brooks' theorem gives \(\chi(G)\le\Delta(G)\).” Check connectedness and verify that the graph is neither complete nor an odd cycle before using the theorem.
• “The maximum-degree bound is \(\Delta(G)\).” The general bound is \(\Delta(G)+1\). The stronger \(\Delta(G)\) conclusion requires an applicable result, such as Brooks' theorem, or a separate argument.

The central habit is to distinguish what each piece of evidence actually establishes. A proper coloring supplies an upper bound; a clique supplies a lower bound; and a theorem supplies a bound only when its assumptions hold. An exact chromatic number is justified when the bounds meet, not merely when one plausible-looking calculation is available.