Motivation
A graph can have one very high-degree vertex while still being easy to color. What matters for a suitable greedy order is not its largest initial degree, but whether a low-degree vertex can always be removed from what remains. Reversing such a deletion order limits the number of already colored neighbors at every step.
Euler's planar edge bound gives exactly that kind of reusable low-degree guarantee. It immediately yields six colors. To obtain five, a vertex of degree five presents the only difficulty: its neighbors might already use every color. Contracting two nonadjacent neighbors forces them to share a color in a smaller planar graph, freeing one color for the deleted vertex. The proof will make clear why ordinary contraction cannot always be undone without extra care.
The argument uses the simple planar edge bound obtained from Euler's formula. No four-color theorem proof is claimed.
Definitions
Definition 10.4.1
(Degeneracy and deletion order)
A finite simple graph is -degenerate, for a nonnegative integer , if every nonempty subgraph has a vertex of degree at most . Degrees here are measured within that subgraph. A degeneracy deletion order removes a vertex of current degree at most at each step until no vertices remain.
A proper vertex coloring assigns one color to each vertex and assigns different colors to adjacent vertices. Greedy coloring in a prescribed order gives each vertex the first available color not already used at its colored neighbors.
It is enough to test induced subgraphs for degeneracy. Indeed, in any subgraph on a chosen vertex set, its degrees are at most the degrees in the induced graph on that set. A low-degree vertex there remains low-degree after further edges are omitted. The property is inherited when vertices or edges are deleted.
Definition 10.4.2
(Edge contraction with simple-graph cleanup)
Contracting an edge identifies its two endpoints into one vertex, retains every other incidence, and then deletes loops and combines parallel edges if the intended result is simple. Planarity is preserved: in a plane drawing, shrink the chosen edge within a thin neighborhood of that edge and its endpoints, carrying incident edge ends with it. Curves can be kept separate away from their common new endpoint. Erasing loops or duplicate edges does not introduce crossings.
This local drawing operation establishes planarity of the contracted graph, not a general rule for lifting its coloring. If formerly adjacent vertices are later assigned the merged vertex's one color, their original edge would violate properness. We will contract a three-vertex configuration while lifting colors only to two originally nonadjacent vertices.
Theorem/Proposition
Theorem 10.4.3
(Degeneracy orders give a controlled greedy coloring)
A graph is -degenerate exactly when its vertices admit a deletion order with at most later neighbors per vertex. Reversing that order and coloring greedily uses at most colors. Every finite simple planar graph is five-degenerate and hence six-colorable.
For planar input represented by adjacency lists, a degree-maintained queue gives the deletion order and a six-coloring in time. This algorithm constructs a coloring; it does not certify planarity of arbitrary input merely by finding such an order.
Theorem 10.4.4
(Five-color theorem by contraction)
Every finite simple planar graph has a proper vertex coloring from a palette of five colors. The result includes disconnected and empty graphs. Its proof uses induction, Euler's degree bound and a contraction of two nonadjacent neighbors of a degree-five vertex.
A six-coloring algorithm and a five-color existence proof are different outputs with different constructions. The latter proof is constructive, but no optimized implementation bound for its repeated contraction and lifting is asserted here. Neither theorem says five colors are necessary for every planar graph.
Proof sketch or proof idea
Proof
(Deletion orders and reverse greedy coloring)
For a -degenerate graph, repeatedly choose a low-degree vertex in the remaining induced subgraph. Its current neighbors are exactly its later neighbors in the deletion order. Conversely, given such an order, take any nonempty subgraph and select its earliest vertex. All its neighbors in that subgraph occur later, so its degree there is at most . This proves the equivalence.
In reverse order, a vertex has at most already colored neighbors. They forbid at most colors, leaving one of available. Whenever a vertex is colored, it avoids all previously colored neighbors. Thus every edge has different endpoint colors once both endpoints are colored.
Proof
(Planar five-degeneracy and the linear six-coloring)
Every nonempty simple planar subgraph with at least three vertices satisfies the proved bound . Its degree sum is , so some vertex has degree at most five. With one or two vertices the same conclusion follows directly from simplicity. All subgraphs remain planar. Thus the low-degree observation applies repeatedly, not just at the start, proving five-degeneracy.
For the linear deletion algorithm, initialize all current degrees and a queue of vertices of degree at most five. On removing one, decrement each surviving neighbor's degree and queue a neighbor when it first crosses down to five. Degrees never increase, so a vertex needs to enter only once. Each edge causes only constantly many degree updates, and the planar low-degree guarantee prevents an empty queue while vertices remain. In the reversed order, inspect neighbors and use a six-entry color marker; that also costs .
Proof
(Five colors by contracting a nonadjacent pair)
For five colors, induct on vertex count. The empty graph is already colored. In a nonempty planar graph choose a vertex of degree at most five. If it has degree at most four, delete it, color the smaller graph by induction, and assign it a color absent from its at most four neighbors.
It remains to handle degree exactly five. Two of its neighbors, say , are nonadjacent. Otherwise those five neighbors would induce , impossible in a planar graph: its ten edges violate the simple planar bound of nine on five vertices. Contract and in succession, merging into one vertex, and perform simple-graph cleanup. The resulting graph is planar and has two fewer vertices, so it has a five-coloring by induction.
Restore every original vertex except , giving and the merged vertex's color and keeping the other colors. This is proper on . The two restored vertices have no edge between them, and every edge from either to another original vertex survived as an edge from the merged vertex to that vertex. No remaining conflict is possible.
Among the five neighbors of , the pair now shares one color; the other three contribute at most three additional colors. At most four colors are therefore forbidden at . Choose the fifth available color to finish the induction. The merged vertex represented during the contraction, but the lifting deliberately leaves original uncolored until this final step.
Proof X-ray
Only the nonadjacent pair inherits the merged color
Three hypotheses are used at three different points. Planarity supplies the vertex of degree at most five through the simple bound , and planarity again excludes , so two neighbors of are nonadjacent. Closure of planar graphs under contraction is what lets the induction hypothesis apply to the graph with merged; five-degeneracy alone would not suffice, since is five-degenerate. Nonadjacency of and is what makes the lift proper: an edge would join two vertices of the same color, and giving the merged color to as well would clash with and , so is left uncolored.
The count then closes the induction. After lifting, the five neighbors of show at most four colors because and agree, so one color of five is free. With six neighbors the same move would leave up to five forbidden colors, which is why the argument needs degree five and not merely a small degree.
Why the proof does not become a four-color proof
Euler's bound supplies a vertex of degree at most five; it does not let us assume the degree is at most three. Merging one pair among five neighbors reduces their possible color count to four. That leaves an available color in a palette of five, but may leave none in a palette of four. The induction therefore proves precisely its stated bound. A different theorem cannot be obtained by relabeling the palette size at the end.
The contraction step also uses more than degeneracy. It needs the smaller contracted graph to remain inside the planar family so induction can be applied to that graph. An arbitrary five-degenerate graph can require six colors, as the complete six-vertex graph shows. The family is closed under the proof's graph operation; that structural closure supplies information absent from a deletion order alone.
Worked examples
Worked example 10.4.5
(Degeneracy avoids an excessive maximum-degree bound)
A star with one center and any positive number of leaves is one-degenerate. A nonempty subgraph with an edge has a leaf of degree one, and an edgeless subgraph has degree zero. Delete leaves before the center, then color in reverse: the center receives one color and every leaf a second. The maximum degree can be arbitrarily large, yet this order always uses two colors. The edge present proves one color cannot suffice.
Worked example 10.4.6
(Contracting a five-neighbor wheel center)
Take a five-vertex rim and hub . Choose nonadjacent rim vertices and merge them with into vertex . The other remaining vertices are . In the simplified graph, joins all three and there is also edge .
Color with one, with two, and with three. Lift color one to , retain the others, and give color four. This is a proper original coloring. Four are actually necessary here: the odd rim needs at least three, all of which are forbidden at its universal hub. The general five-color bound need not be sharp on an individual graph.
Worked example 10.4.7
(Bad greedy orders can use arbitrarily many colors on trees)
Let be a single rooted vertex. For , take disjoint copies of and add a new root adjacent to their roots. The result is a tree: every old component attaches once to the new vertex. Induction gives .
Color each copied tree in its recursively specified order, then the new root last. The copied roots receive colors one through , so the new root receives color . Thus this greedy order uses colors on a tree, although for the tree is two-colorable. A planar graph receiving many greedy colors may simply have been processed in a poor order; it does not refute the existence bound.
Concept lensStructural
Deletion and contraction use different kinds of closure
Low-degree deletion controls the reverse greedy step. Contraction changes which vertices must share a color when a solution is lifted. Planar graphs remain planar under both operations, allowing induction on different smaller graphs. Each operation preserves the property needed for the next step, while their color-lifting rules are different.
Common mistakes
Counterexample mode
A coloring of a minor cannot always be lifted unchanged
Contract an edge of a triangle. After removing the resulting parallel-edge duplication, the graph is a single edge and is two-colorable. The triangle is not two-colorable: its third vertex is adjacent to both endpoints of any edge. Restoring the contracted adjacent endpoints with the same color fails. The five-color proof avoids that error by sharing a color only between originally nonadjacent neighbors and coloring the middle vertex separately.
Common mistake
(A low-degree vertex is not a degeneracy order)
Do not mistake a low initial degree for a guaranteed low-degree order in all remaining graphs. Attach one pendant vertex to : the graph has a vertex of degree one, but after that vertex is deleted every remaining vertex has degree four. The graph is four-degenerate and not one-degenerate, and it needs five colors.
Common mistake
(A successful order does not certify planarity)
Do not assume that a coloring or a deletion order proves planarity. On the queue algorithm still finds an order with at most five later neighbors per vertex and outputs a six-coloring, yet has fifteen edges, more than the planar bound twelve.
Common mistake
(Loops leave the theorem's domain)
Simplicity is essential to the degree and coloring statements: a graph with a loop has no proper vertex coloring under the ordinary adjacent-endpoint rule, whatever the palette size, because the looped vertex is adjacent to itself.
Summary
Degeneracy turns repeated low-degree deletion into a controlled reverse greedy order. Euler's bound supplies that order for a linear six-coloring of planar graphs. A carefully lifted contraction handles the degree-five obstruction and proves the five-color theorem, while exposing exactly why the same argument does not prove four colors.
Exercises
Quick check
(Show that the complete graph on six vertices is five-degenerate but not five-colorable. Explain which extra property the planar contraction proof uses.)
Check every subgraph's degree bound and the coloring requirement of a clique.
Solution · Answer
Every subgraph of has at most six vertices and hence degree at most five, so it is five-degenerate. All six vertices are pairwise adjacent and therefore require six distinct colors. It is not planar, since fifteen edges exceed the bound twelve. The planar proof uses preservation of planarity under contraction and the absence of a five-clique among the chosen neighbors; those facts do not follow from five-degeneracy alone.
Quick check
(Explain why merely obtaining a vertex of degree at most six would not complete the same five-color induction by merging one nonadjacent pair of neighbors.)
Count the possible distinct neighbor colors after the merge.
Solution · Answer
With six neighbors, merging one nonadjacent pair forces only those two to share a color. The remaining four neighbors could use four further colors, leaving as many as five forbidden colors at the deleted vertex. A five-color palette then has no guaranteed free color. The argument needs the degree-five conclusion to reduce the forbidden count to at most four. This explains a limit of the proof, not a claim that every degree-six configuration actually requires six colors.
Quick check
(Prove the degeneracy upper bound is sharp for an odd cycle with five vertices. Give an explicit optimal coloring and identify why a looped version is outside the theorem.)
Compare two-degeneracy with the impossibility of alternating two colors around an odd cycle.
Solution · Answer
The five-cycle has degree two, and every subgraph has a vertex of degree at most two, so it is two-degenerate. Alternating two colors around its five edges would return to the starting vertex with the opposite required color, impossible. In cyclic order, colors one, two, one, two, three give a valid three-coloring. Hence its chromatic number is three, achieving . Adding a loop makes its endpoint adjacent to itself, so no color can satisfy properness there; the resulting graph is not simple and is excluded from both theorem hypotheses.