Build a shadow graph and check its coloring

Try

Start with a five-cycle: vertices v₁,v₂,v₃,v₄,v₅ joined by edges 12,23,34,45,51. Here “12” abbreviates the undirected edge between v₁ and v₂. There are no other edges. The graph has no triangle: each vertex has only its two cycle neighbors, and those two are not adjacent.

A proper coloring of this cycle is (1,2,1,2,3), in vertex order. Check all five edges, especially the closing edge 51. A coloring is evidence only after every edge has been checked. A picture with attractive colors can still contain a conflict.

Now create a new graph. Keep all five original vertices and edges. Add five distinct shadow vertices u₁ through u₅, and one new apex w. Each shadow uᵢ connects to the original neighbors of vᵢ. Thus u₁ connects to v₂ and v₅, not to v₁. Finally join w to every shadow. Add no edges between shadows and no edges from w to originals. This is the Mycielski construction, described here as a shadow graph.

Before counting, predict whether the new apex creates triangles. It has five neighbors, but those neighbors are independent: no two are adjacent. Having many neighbors does not by itself create a triangle.

Predict

There are 11 vertices. Predict the number of edges by separating three families rather than counting crossings in a drawing. Crossings are not vertices unless explicitly declared to be vertices.

Give uᵢ the same color as vᵢ, and give w a new color 4. Predict which edges require a new argument. An original edge already has different colors. A cross edge uᵢvⱼ has the same endpoint colors as the base edge vᵢvⱼ that created it. An apex edge has color 4 at one end and one of 1,2,3 at the other. This checks all families and proves the four-color assignment is proper.

It proves the chromatic number is at most four. It does not prove that three colors are impossible. That requires a lower-bound argument about every potential coloring, not just this displayed assignment.

Experiment

Use the explorer to inspect the five-cycle construction. Its labels start at zero: widget v0 corresponds to prose v₁, continuing through widget v4 and prose v₅; shadows use the same shift. The initial all-one assignment is intentionally invalid. Choose “Load four-color witness,” then compare the exact edge check with the three families above. Before changing anything, predict what happens if only w changes to color 1: it conflicts with widget u0 and u2, the two shadows colored 1. Restore color 4. Now change widget v4 from 3 to 1 while leaving v0 at 1. The closing original edge v4–v0 conflicts; the cross edge v4–u0 conflicts too. Work from named endpoints, not from how close the vertices appear. “Reset all colors to 1” returns to the deliberately invalid starting assignment.

Test a coloring of the cycle lift

The original vertices v0–v4 form a five-cycle. Shadow ui is adjacent to the two original neighbors of vi. The apex w is adjacent to every shadow. There are no other edges: in particular, shadows are not adjacent to one another or to their own original vertex. Predict a conflicting edge before changing a color.

Reset all colors to 1Load four-color witness

Color of v0Color 1Color 2Color 3Color 4Color of v1Color 1Color 2Color 3Color 4Color of v2Color 1Color 2Color 3Color 4Color of v3Color 1Color 2Color 3Color 4Color of v4Color 1Color 2Color 3Color 4Color of u0Color 1Color 2Color 3Color 4Color of u1Color 1Color 2Color 3Color 4Color of u2Color 1Color 2Color 3Color 4Color of u3Color 1Color 2Color 3Color 4Color of u4Color 1Color 2Color 3Color 4Color of wColor 1Color 2Color 3Color 4

Fixed graph facts: 11 vertices, 20 edges and 0 triangles. Degrees: v0–v4 each 4; u0–u4 each 3; w has degree 5. Degree sum 40 equals twice the number of edges. These facts do not depend on the selected colors.

Not a proper coloring. 20 conflicting edges; 1 distinct color number currently used (1).

Every conflict: v0–v1 (both 1); u0–v1 (both 1); u1–v0 (both 1); v1–v2 (both 1); u1–v2 (both 1); u2–v1 (both 1); v2–v3 (both 1); u2–v3 (both 1); u3–v2 (both 1); v3–v4 (both 1); u3–v4 (both 1); u4–v3 (both 1); v4–v0 (both 1); u4–v0 (both 1); u0–v4 (both 1); w–u0 (both 1); w–u1 (both 1); w–u2 (both 1); w–u3 (both 1); w–u4 (both 1).

Complete edge list; each undirected edge appears once

Edge	Endpoint color numbers	Different?
v0–v1	1, 1	No — conflict
u0–v1	1, 1	No — conflict
u1–v0	1, 1	No — conflict
v1–v2	1, 1	No — conflict
u1–v2	1, 1	No — conflict
u2–v1	1, 1	No — conflict
v2–v3	1, 1	No — conflict
u2–v3	1, 1	No — conflict
u3–v2	1, 1	No — conflict
v3–v4	1, 1	No — conflict
u3–v4	1, 1	No — conflict
u4–v3	1, 1	No — conflict
v4–v0	1, 1	No — conflict
u4–v0	1, 1	No — conflict
u0–v4	1, 1	No — conflict
w–u0	1, 1	No — conflict
w–u1	1, 1	No — conflict
w–u2	1, 1	No — conflict
w–u3	1, 1	No — conflict
w–u4	1, 1	No — conflict

Load the four-color witness: originals and shadows both use the ordered list 1,2,1,2,3, and w uses 4. Then change only w to 1. Predict which two edges become conflicts and check the list. Reset assigns color 1 to every vertex; this is a complete but invalid assignment, not an uncolored graph.

All twenty edges are tested exactly for this assignment. The fixed graph has no triangles, but that fact alone does not imply three-colorability. The explorer does not search all colorings or prove a general chromatic theorem. Colors and controls are temporary; no work is saved and no completion is awarded.

As a separate paper construction, replace the five-cycle by the four-cycle with edges 12,23,34,41. List all eight cross edges and all four apex edges. Color originals and their corresponding shadows (1,2,1,2), and use color 3 for the apex. Determine every degree before opening the feedback.

Check the four-cycle construction

There are 9 vertices and 16 edges: four original, eight cross and four apex edges. Every original has degree 4, every shadow degree 3, and the apex degree 4. The degree sum is 4·4+4·3+4=32, twice the edge count. The copied coloring is proper for the same edge-family reasons. It proves an upper bound of three colors, not a new general theorem about the minimum.

Understand

Let the finite simple undirected base graph have n vertices, m edges and original degrees d₁,…,dₙ. The original vertices, shadow vertices and apex are disjoint objects, even though a shadow’s subscript matches an original’s. The construction uses that correspondence to determine adjacency; it does not identify the two vertices.

Counts and degrees. Two copies of n vertices plus the apex give 2n+1 vertices. Each base edge remains and creates two cross edges, giving m+2m edges before the n apex edges are added. Thus there are 3m+n edges. The two cross edges from one base edge are different because the endpoints have different copy types. Distinct base edges cannot produce duplicate cross edges: a cross edge uᵢvⱼ uniquely identifies its generating base edge vᵢvⱼ. None can be an original or apex edge.

An original vᵢ meets its dᵢ original neighbors and the dᵢ shadows corresponding to those neighbors, so its degree is 2dᵢ. Shadow uᵢ meets those dᵢ original neighbors and the apex, so its degree is dᵢ+1. The apex degree is n. Since the original degree sum is 2m, the lifted degree sum is 2(2m)+(2m+n)+n=6m+2n, agreeing with twice 3m+n. This agreement checks bookkeeping; the adjacency argument is what establishes the formulas.

Why triangle-freeness is preserved. Suppose a triangle exists in the lifted graph. If it contains w, its other two vertices must be shadows, but shadows are not adjacent. If it avoids w and contains at least two shadows, the same missing shadow-shadow edge rules it out. If it contains no shadows, it is an original triangle already present in the base.

The remaining case has exactly one shadow uᵢ and two originals vⱼ,vₖ. Their triangle edges say that vᵢ is adjacent in the base to both vⱼ and vₖ, and that vⱼ is adjacent to vₖ. The indices are distinct: j differs from k because they name distinct triangle vertices; i differs from both because a simple graph has no loop and hence the construction has no edge uᵢvᵢ. These three base edges therefore form a genuine base triangle. A triangle-free base excludes this last case too.

The argument uses all the adjacency restrictions. The apex needs independent neighbors; the shadows need no mutual edges; a shadow supports exactly the original neighbor set of its corresponding vertex. The phrase “shadow supports a base neighborhood” describes these particular edges, not a visual resemblance. Conversely, a base triangle survives among the originals, so the lift is triangle-free exactly when its base is triangle-free.

Apply

Diagnose an incorrect construction that copies every base edge between the corresponding shadows. If the base has edge 12, then u₁u₂ becomes an edge, and w,u₁,u₂ is immediately a triangle. The claimed triangle-free theorem has lost a hypothesis about the construction itself.

A different mistake adds uᵢvᵢ. Whenever vᵢvⱼ is a base edge, the already-present edge uᵢvⱼ combines with the new diagonal uᵢvᵢ and the original vᵢvⱼ to form a triangle. Explain why these two mistakes invalidate different steps of the case analysis.

For a boundary case, use a base with three isolated vertices. The originals remain isolated. Each shadow has degree one because it is joined to w, and w has degree three. The graph has seven vertices and three edges, consistent with 2n+1 and 3m+n when n=3,m=0. If the base has no vertices at all, the construction still adds one isolated apex. Counts remain valid, but arguments about a nonempty base’s color requirements must state their domain separately.

Check a coloring certificate without a drawing

For any proper k-coloring of the base, color each shadow like its corresponding original and assign a new apex color. Original and cross edges inherit distinct base endpoint colors; apex edges use the new color. This is a proper coloring with at most k+1 colors. Its proof is independent of how the graph is laid out. Establishing an exact chromatic increase needs the separate lower-bound proof in the following lesson.

Continue

The practice asks you to list complete edge sets for small changed bases, verify a color certificate, derive general counts, and repair false construction rules. A finite color assignment supplies an upper bound; it cannot establish a lower bound by itself. Keep those two kinds of evidence separate.

The next lesson will use the apex’s color to turn a hypothetical coloring of the shadow graph into a coloring of the base. That argument explains the chromatic increase. The construction and triangle-case proof here provide the structural facts it will need, without assuming that a crowded drawing requires more colors.