When Seventeen Vanishes

A complex-number laboratory for graph 3-coloring.

What problem are we trying to solve?

A proper 3-coloring assigns one of three colors to every vertex of a graph. The rule is simple: the two endpoints of every edge must have different colors. We want a numerical test that recognizes when this rule is satisfied.

Instead of storing colors as names, we will store them as complex numbers. Nothing below requires previous experience with complex numbers; here is all the arithmetic we need.

Complex numbers from scratch

The symbol i is defined by i² = −1. A complex number has the form z = a + bi, where a and b are ordinary real numbers. You can picture it as the point (a,b): move a units horizontally and b units vertically.

z = a + bi   ↔   point (a,b)   ·   i² = −1

The complex conjugate keeps the horizontal part and reverses the vertical part. It is usually written z̄ (“z bar”); this page also spells it out as conjugate(z). For example, conjugate(3 + 2i) = 3 − 2i. Geometrically, this reflects the point across the horizontal axis.

Conjugation is useful because multiplying a number by its conjugate produces an ordinary nonnegative real number:

(a + bi)(a − bi) = a² + b²    so    z conjugate(z) = |z|²

Here |z| = √(a² + b²) is the distance from the point z to the origin. The unit circle consists of the points at distance 1. Thus, if v is on the unit circle, then v conjugate(v) = |v|² = 1.

To divide by a complex number, multiply the top and bottom by its conjugate. This makes the denominator real—just like rationalizing a denominator containing a square root:

u/v = [u conjugate(v)]/[v conjugate(v)] = [u conjugate(v)]/|v|²

On the unit circle |v|² = 1, so this becomes the especially simple rule u/v = u conjugate(v). For instance, 1/i = −i = conjugate(i). You can think of u/v as the rotation that carries the point v to the point u.

We now encode the three colors by the three cube roots of unity—the three complex numbers whose cubes equal 1. They are equally spaced on the unit circle. At a graph vertex x, we store one of them as zx:

red ↔ 1   ·   green ↔ ω = −1/2 + (√3/2)i   ·   blue ↔ ω² = −1/2 − (√3/2)i    where    ω³ = 1

The question. Suppose u,v ∈ {1, ω, ω²}. Can we write one formula over the complex numbers that recognizes whether the two colors agree?

Find Δ3(u,v) such that   Δ3(u,v) = 1 if u = v,   and   Δ3(u,v) = 0 if u ≠ v.

Yes. Use the unit-circle division rule from the primer and set r = u conjugate(v) = u/v. If u = v, then u/v = 1. Conversely, if u/v = 1, multiplying by v gives u = v. Thus r = 1 exactly when the colors agree. The desired formula is

Δ3(u,v) = (1/3)[1 + u conjugate(v) + (u conjugate(v))²]

Worked example: different roots. Take u = ω and v = ω². Since conjugate(ω²) = ω, their relative color is u conjugate(v) = ω². Hence

Δ3(ω,ω²) = (1/3)(1 + ω² + ω⁴) = (1/3)(1 + ω² + ω) = 0.

Check the equal case. If u = v = ω, then u conjugate(v) = |ω|² = 1, so

Δ3(ω,ω) = (1/3)(1 + 1 + 1) = 1.

Now return to the graph. For an edge joining vertices x and y, substitute u = zx and v = zy. Define C3(x,y) = Δ3(zx,zy). A properly colored edge contributes 0; a same-color conflict contributes 1. Therefore E = Σxy in edges |C3(x,y)|² is exactly the number of conflicting edges, and E = 0 exactly for a proper 3-coloring.

The lab starts with three colors. If you choose q colors, it uses the same construction with the q-th roots of unity and Cq(u,v) = (1/q) Σq−1j=0 rj.

1 · EncodeStore each vertex color as a complex root of unity.
2 · Test an edgeForm the relative color r and add 1 + r + r².
3 · Count conflictsGood edges give 0; same-color edges give 1.

Select an edge in the graph or menu to replay its walk. Edges with the same relative color r have the same walk.

Click a vertex to cycle its color
The arrows 1, r, r², ... for the selected edge
Why does the edge test give exactly 0 or 1?

For the q-color version, let u and v be two q-th roots of unity and put r = u conjugate(v). Since |v| = 1, we have conjugate(v) = 1/v, so r = u/v. In particular, r = 1 exactly when u = v.

  1. Both colors satisfy uq = vq = 1. Therefore rq = (u/v)q = 1.
  2. If the colors differ, then r ≠ 1. Let S = 1 + r + r² + ⋯ + rq−1. Multiplying by r − 1 makes all the middle terms cancel:
    (r − 1)S = rq − 1 = 1 − 1 = 0.
    Because r − 1 ≠ 0, the only possibility is S = 0. After dividing by q, the edge test is still 0.
  3. If the colors agree, then r = 1. Every one of the q terms in S equals 1, so S = q. Dividing by q makes the edge test equal to 1.

Thus Cq is a same-color indicator: it is 1 on a conflicting edge and 0 on a properly colored edge. Consequently Σ |Cq|² counts conflicts exactly.

Things to try

  1. Can you make the Petersen graph's energy 0 using its three colors?
  2. Choose the Speyer graph. Can you beat energy 1 with three colors? What changes with four?
  3. Switch to 17 colors on one edge and change B once. Why do all 17 arrows close?
  4. Choose 4 colors and put A and B at opposite roots. The arrows alternate: 1−1+1−1.
  5. Can a pentagon have energy 0 with 2 colors? With 3?

Planted cliques—and their complements

Both examples begin with a fixed seeded sample from G(n, p): every pair of vertices has probability p of being an edge. The slider starts at p = 0.17 and rebuilds both random backgrounds. In the first sample, n = 51. We secretly choose 17 vertices and add every missing edge between them, planting a K17 with (17 choose 2) = 136 internal edges.

The second sample has n = 64. We choose six of its vertices and complete all the edges between them, planting a K6. These are fixed seeded samples, so the pictures remain stable while you compare them.

The graph on the right is the exact complement G̅ = Kn ∖ G: start with the complete graph and subtract every edge of G. Thus the planted clique becomes an independent set. In the primal graph, its vertices need different colors; in the complement, those same vertices may all share one color. Here “dual” means this complementary view, not the planar dual of an embedded graph.

Primal G: K₁₇ uses 17 different vertex colors
Complement K₅₁ ∖ G: the independent set uses one color

In G, the planted vertices use distinct colors and their clique edges are highlighted. In G̅, the same vertices all use one color and have no edges between them. The remaining vertices are left neutral; this illustrates the planted set, not a coloring of the entire random graph. Every vertex pair is an edge in exactly one picture.

Color the four large graphs

This is the same conflict-counting experiment as the smaller coloring lab, but the graph now uses the full width and the complex-number panel is omitted. Click a vertex to cycle its color. Red edges are color conflicts; the energy is their total number. The probability slider above controls the random-edge density in all four views.

Primal graph on 51 vertices

Planted vertices have an extra outline. The reset state gives a different color to every planted-clique vertex in the primal graph, and one shared color to the corresponding independent set in the complement. Background vertices are also colored, so the displayed energy tests the entire graph.

Planar obstruction adapted from David E Speyer, “Planar non-3-colorable graphs,” Mathematics Stack Exchange, answer 630493, version 2020-06-08 (CC BY-SA 4.0).