Try
A five-cycle needs three colors: alternating two colors returns to the start with a conflict, while the consecutive colors 1,2,1,2,3 work. It contains no triangle. Can we make a graph that still has no triangle but needs four colors? A failed attempt to color one drawing with three colors is not enough; we need a reason every three-color assignment fails.
Use the construction from the preceding lesson. For each original vertex vᵢ, add a shadow uᵢ. Keep every original edge vᵢvⱼ and add the two cross edges uᵢvⱼ and uⱼvᵢ. Add an apex w adjacent to every shadow. There are no shadow-shadow edges and no apex-original edges. Call the resulting graph M(G). Throughout, graphs are finite, simple and undirected.
Predict
Given a proper coloring of G with k colors, predict how to color the shadows and apex using at most one additional color. Then consider the harder direction: if someone claims to color M(G) with only k colors, what information does the apex supply about every shadow?
A proper coloring assigns different colors to the endpoints of every edge. The chromatic number χ(G) is the smallest number of colors that suffices. Producing a coloring proves an upper bound; proving impossibility with fewer colors establishes the lower bound. We need both to identify χ exactly.
Experiment
For a five-cycle, use this explicit four-color certificate. Check the retained cycle edges, both cross edges contributed by each cycle edge, and all five apex edges separately.
| Position i | 1 | 2 | 3 | 4 | 5 |
|---|
| Original vᵢ color | 1 | 2 | 1 | 2 | 3 |
|---|
| Shadow uᵢ color | 1 | 2 | 1 | 2 | 3 |
|---|
| Apex color | 4, different from every shadow |
|---|
Now perform a proof action rather than searching more assignments. Imagine an arbitrary proper three-coloring of this lifted graph and rename the apex color “3.” Every shadow must then have color 1 or 2. On the original cycle, replace any original color 3 by that vertex’s shadow color. For each original edge, ask which endpoints could be changed and which cross edge certifies their new inequality. The next argument explains why this would produce an impossible two-coloring of the cycle.
Understand
For every finite nonempty simple graph G, χ(M(G))=χ(G)+1. First let k=χ(G). Copy a proper k-coloring of G to the corresponding shadows and give the apex a new color. Each cross edge corresponds to an original edge, so its endpoints inherit different colors. Apex edges meet the new color. There are no other types to check. This proves χ(M(G))≤k+1.
Suppose instead that M(G) can be colored with at most k colors. Name the available colors 1 through k, allowing unused names if necessary, and rename the apex color k. No shadow has color k. Define a new coloring of G: keep each original color other than k, and replace color k at vᵢ by the color of uᵢ. All resulting colors are among 1 through k−1.
Why is the new coloring proper? For any original edge vᵢvⱼ, its two endpoints could not both originally have color k, because the assumed lifted coloring was proper. If neither changes, their colors remain different. If only vᵢ changes, the cross edge uᵢvⱼ ensures its replacement color differs from the unchanged color at vⱼ. The case where only vⱼ changes is symmetric. This exhausts all possibilities and gives a proper coloring of G with k−1 colors, contradicting the definition of k.
For k=1, the assumed one-coloring already fails on any apex-shadow edge, which exists because G is nonempty. The replacement argument’s empty palette is likewise impossible on a nonempty G. For an empty G, handle the construction separately: only the apex remains, giving chromatic number 1 instead of 0. An edgeless nonempty G has chromatic number 1 and its lift is a nonempty star plus isolated originals, so its chromatic number is 2.
The extra-color theorem does not require G to be triangle-free. That is a separate preservation property. A triangle containing the apex would need an edge between two shadows, which does not exist. A triangle cannot contain two shadows for the same reason. A triangle with one shadow and two originals would imply a triangle of corresponding originals in G; those three are distinct because no shadow joins its own original in a simple loop-free input. A triangle with only originals was already in G. Thus triangle-free inputs remain triangle-free.
Apply
Start with the five-cycle and repeat the construction. It begins with five vertices, five edges and chromatic number 3. Each step replaces n vertices by 2n+1 vertices. Each old edge remains and contributes two new cross edges, while the apex adds n new edges, so the new edge count is 3m+n. The first two lifted sizes are (11 vertices,20 edges) and (23 vertices,71 edges), with chromatic numbers 4 and 5. Predict and justify the third row before checking it in practice.
Induction gives a triangle-free finite graph with chromatic number 3+t after t lifts. This proves that triangle-free graphs have no universal finite bound on their chromatic numbers. It does not say that one fixed finite graph requires infinitely many colors.
For a changed proof diagnosis, remove the apex. Copying the original colors to shadows now colors the entire remaining graph with k colors, and its original induced copy of G still requires k. Remove only the cross edges instead: the apex and shadows form a star disconnected from G. Its chromatic number is max(k,2). These changes show why both the apex restriction and the cross-edge replacement guarantee are necessary to this proof mechanism.
Continue
In the practice, distinguish construction checks, a displayed coloring and a universal coloring obstruction. When a recoloring argument changes vertices, inspect every possible edge case rather than assuming that fewer color names preserve properness. The theorem establishes a family-wide lower bound through a contradiction about an arbitrary coloring; neither an attractive diagram nor a bounded unsuccessful search supplies that conclusion alone.
