Vertex Coloring and Chromatic Number
A proper -coloring of assigns one of colors to each vertex so that every edge joins two DIFFERENT colors. is -colorable if a proper -coloring exists, and the chromatic number is the smallest such . If contains a clique (a set of pairwise adjacent vertices) of size , then : every pair inside a clique needs a different color, so a clique of size alone forces at least colors.
Coloring is the right language whenever some pairs of objects conflict and must be kept apart: exam slots for courses with common students, radio frequencies for nearby towers, registers for variables alive at the same time. Topic 7's bipartite graphs are exactly the graphs with , and the odd-cycle theorem there is really the first chromatic-number computation in this course, stated in the language of two colors. The clique bound is cheap to check — exhibit any mutually adjacent set — but it runs only ONE direction: a graph can need far more colors than its largest clique supplies, which is exactly the misconception below. Pinning down exactly, rather than merely bounding it, is in general a hard computational problem; the rest of this topic builds the tools — greedy orderings, Brooks' theorem, the chromatic polynomial — that make it tractable for the graphs that matter.
Every pair of vertices in is adjacent, so every vertex needs a color of its own: . The clique bound gives immediately, since the WHOLE vertex set is itself a clique; and colors obviously suffice (one color per vertex), so the bound is tight, with equality.
(vertices in a ring) is an odd cycle, hence not bipartite (Topic 7), so : no proper -coloring exists. Three DO suffice: color with color , with color , and with color . The edges then get — every pair different. So exactly, one more than its clique number (it has no triangle at all).
Does the Petersen graph (Topic 1) need more than colors? It contains -cycles — the outer rim is one — so by the odd-cycle theorem it is not bipartite and . A -coloring is easy to exhibit: give the outer rim the pattern (so , , ) and the inner star the pattern (so , , , ). Checking all edges — the rim edges, the spokes , and the inner "pentagram" edges — confirms every single one joins two different colors. So .
Assuming because the clique bound is so often tight. The -cycle above is the standard counterexample: (no three vertices are pairwise adjacent — it has no triangle at all) yet . Odd cycles longer than a triangle are exactly this: triangle-free, so the clique bound only promises , while the parity argument for odd cycles forces . The gap between and can be made arbitrarily large for cleverly built graphs (Mycielski's construction, beyond this course) — a clique is a LOWER bound, never the whole story.
Let be a hub vertex joined to every vertex of a -cycle rim (a wheel on vertices, edges in all). Find .
Show the answerHide the answer
The rim is an even cycle, hence bipartite, so it can be properly -colored, alternating around the ring. The hub is adjacent to EVERY rim vertex, so it needs a color different from both and already in use — a third color, . Three colors suffice (rim in , hub in ), and the hub together with any two ADJACENT rim vertices forms a triangle, a clique of size forcing by the clique bound. So .
Greedy Coloring and Brooks' Theorem
Fix an order of . The greedy coloring assigns the SMALLEST color not already used by an earlier neighbor of . Since has at most neighbors, at most colors are ever forbidden, so one of the first colors is always free:
Brooks' theorem sharpens this for connected : , UNLESS is a complete graph or an odd cycle, in which case .
The bound costs nothing to prove (the full argument is in Why It Works) and holds for every graph and every vertex order, which is exactly why it is usually far from the truth. Brooks' theorem is the surprising half: it says this trivial, order-independent bound is almost NEVER the best you can do — only climbs all the way to for the two families where it is forced by Section 1's clique bound. needs colors because the whole graph is one clique; an odd cycle needs colors () because the odd-cycle theorem rules out . Every other connected graph, however large is, can be colored with only colors — a genuinely hard theorem to prove, though easy to use.
Order the vertices of any way, say . Vertex has no colored neighbors yet, so it gets color . Vertex is adjacent to (color used), so it needs color . Vertex is adjacent to (colors used), so it needs color . Vertex is adjacent to (colors used), so it needs color . No order could do better here, since is one of Brooks' two exceptions: but , as Section 1 already established directly.
The Petersen graph (pictured in the previous section) has , and it is neither complete nor an odd cycle, so Brooks' theorem guarantees — already a real improvement over the trivial bound . The -coloring exhibited there shows this sharper bound is achieved with equality: , exactly as Brooks promises for a graph outside the two exceptional families.
Let the triangular prism have two triangles and joined by the matching ( edges on vertices, every vertex of degree , so ). It is not complete ( would need edges, not ) and not an odd cycle, so Brooks' theorem gives . It also contains the triangle , so the clique bound gives . Together, exactly: color with , with , and with . Checking all edges — — gives the color pairs , every one two different colors.
Believing the bound IS the value of , or that any vertex order realizes it. Take the bipartite "crown" graph on with adjacent to whenever ( edges, ); being bipartite, . Greedily coloring in the INTERLEAVED order : ; (no colored neighbor yet) too; is adjacent to (color ) ; is adjacent to (color ) ; is adjacent to BOTH (colors ) ; likewise . This order burns colors on a graph that only ever needs — the trivial bound is reached only because the order was chosen badly, not because colors were actually necessary.
What does Brooks' theorem say about (complete bipartite, both parts of size , so ), and is that bound tight?
Show the answerHide the answer
is neither a complete graph (it has no edges within a part) nor an odd cycle, so Brooks' theorem guarantees . But is bipartite (Topic 7), so in fact — far below the Brooks bound. Unlike the Petersen graph and the prism above, where Brooks' bound was exact, here it is not tight at all: , not .
The Chromatic Polynomial
The chromatic polynomial counts the proper colorings of using (up to) available colors. For any edge ,
where deletes and deletes and merges into one vertex. The empty graph on vertices has . For every graph, is genuinely a polynomial in (Why It Works), and is the smallest POSITIVE integer with .
The recurrence comes from splitting the colorings of into two disjoint piles: those where and already differ, which are exactly the proper colorings of (the edge costs nothing extra to add back), and those where and agree, which are exactly the colorings of the merged graph . So , which rearranges into the boxed formula. Evaluating one polynomial at every integer answers every -coloring question for at once, including the hardest one: for and from onward, so the chromatic number is simply the polynomial's smallest positive root among the integers.
Let the paw be a triangle with a fourth vertex attached only to . Any proper coloring of the triangle extends to in exactly ways ( only has to avoid the single color used at ), so . Since (color the first vertex ways, the second ways avoiding it, the third ways avoiding both), . At : . At the factor vanishes, giving — confirming , exactly what the triangle alone already demanded.
Every cycle obeys (derived from the same recurrence in Why It Works). For the -cycle from Section 1, is odd, so . At : — NO proper -coloring exists, confirming exactly as the odd-cycle theorem forced. At : , a positive count, confirming colors do suffice. The polynomial turns positive exactly at .
Let the "diamond" be minus the edge : vertices with edges . Deleting edge leaves , which is the -cycle , so . Contracting edge merges into one vertex adjacent to both and (the duplicated edges and each collapse to one), leaving a -vertex path, so . By deletion-contraction,
Cross-check by counting directly: color in ways, in ways (adjacent to ), then and EACH avoid only (they are not adjacent to each other) in ways apiece, giving — the same polynomial. At : ; at : the factor vanishes, so , matching the triangle (or ) already inside it.
Getting the deletion-contraction sign backwards: writing with a PLUS. The colorings of split into those where 's endpoints already differ (the colorings of itself) and those where they agree (the colorings of ), so it is that equals the SUM — meaning itself is the difference, a MINUS. Using a plus for would claim , falsely suggesting a -coloring exists, when Section 1 already proved has none.
A tree on vertices (Topic 4) is built one edge at a time with no cycles ever closing, so coloring it means coloring a first vertex in ways and then each further vertex avoiding only its one already-placed neighbor, in ways: . Use this for the path on vertices, and evaluate at .
Show the answerHide the answer
Here , so . At : — matching the only two -colorings possible, the alternating patterns and .
Edge Coloring
A proper edge coloring assigns colors to the edges of so that any two edges sharing a vertex get DIFFERENT colors. The chromatic index is the fewest colors this takes. The edges at any vertex all share that vertex, so they alone need different colors: always. Vizing's theorem: for every simple graph — is Class 1 if , Class 2 if .
Edge coloring is secretly vertex coloring one level removed: the LINE GRAPH has one vertex per edge of , with two line-graph vertices adjacent exactly when the two original edges share an endpoint, and by construction. What makes edge coloring special is how narrow Vizing's theorem is: unlike Brooks' theorem, where can sit well below for all sorts of graphs, is ALWAYS within one color of the trivial bound — no graph is ever a worse surprise than that. König's edge-coloring theorem settles the bipartite case outright: every bipartite graph is Class 1, exactly, provable by the same alternating-path machinery as Hall's theorem and the vertex-cover König's theorem (Topic 7, a different theorem sharing only the name). Deciding Class 1 versus Class 2 for a general graph, though, is itself a hard computational problem — Vizing's theorem is cheap to state and expensive to settle.
has (every vertex meets edges), so by the trivial bound. Three colors suffice: split the edges into the perfect matchings , , , one color per matching. Any two edges of the SAME matching share no vertex by definition, so no two same-colored edges ever meet — a proper -edge-coloring. So : is Class .
Label the vertices of as and color edge with . Two edges sharing vertex are and with ; their colors agree only if , impossible for distinct — a genuine proper edge coloring, and it visibly uses all colors (the edges at vertex alone, , already get the different colors ). Since , this shows . And is actually necessary: with only colors, each color class is a matching on vertices, which can cover at most disjoint edges (an odd number of vertices always leaves one unmatched), so colors could cover at most of the edges — too few. So : is Class .
Does the -regular Petersen graph (Topic 1) have , like above? A proper -edge-coloring of a -regular graph must split its edges into PERFECT matchings, one per color, since each color class has to saturate every vertex using exactly one of its incident edges. The Petersen graph has exactly perfect matchings in total (a short exhaustive check); examining all ways to pick three of them shows none are pairwise disjoint with union covering all edges. So no partition into perfect matchings exists, and colors are not enough: . The Petersen graph is the smallest snark — a connected, bridgeless, -regular, Class graph.
Assuming always, since Vizing's window is so narrow that Class feels rare. The odd cycle is a simple, concrete counterexample: , yet no -edge-coloring works — going around its edges, the colors must alternate , but after an ODD number of edges the coloring returns to its start already wearing the wrong color, exactly the odd-cycle argument for vertex coloring in Section 1. A third color is unavoidable: . Odd cycles are Class for the same parity reason they need vertex colors, not .
By König's edge-coloring theorem, every bipartite graph is Class . Use this to find , and exhibit an explicit edge coloring achieving it.
Show the answerHide the answer
has (every vertex meets all vertices on the other side), so König's theorem gives directly. Explicitly: label the parts and and color edge with ; two edges sharing get colors for different , always different, and likewise for two edges sharing a — a proper -edge-coloring using exactly colors.
The Five and Four Color Theorems
Every planar graph satisfies (the Five Color Theorem, proved in full below) and, in fact, (the Four Color Theorem). The bound of is tight — some planar graphs genuinely need all — but NO planar graph, however large or intricate, ever needs a th.
Both theorems lean on the same planar edge bound (Topic 8): a planar graph on vertices has at most edges, so its average degree is under , guaranteeing SOME vertex of degree at most somewhere in the graph. That one fact drives an induction — remove a low-degree vertex, recolor the smaller graph, add the vertex back — and the Five Color Theorem's proof completes this induction cleanly using a trick called a Kempe chain. The Four Color Theorem is the same statement with sharpened to , first proved in 1976 by Appel and Haken with a computer check of roughly unavoidable configurations; no proof short enough for a single chapter is known even today, so this course states it without proving it — the honest thing to do, and a sharper version of the same lesson as Vizing's theorem: some true statements are far cheaper to believe than to settle. Either way, restricting to planar graphs caps at a small constant no matter how many vertices the graph has — a genuinely topological fact, since for graphs in general is unbounded (, from Section 1).
Draw as a wheel: a hub at the center joined to a triangle on the rim ( edges, no crossings — this redrawing shows is planar). The whole graph is a clique of size , so the clique bound (Section 1) forces , and colors obviously suffice, one per vertex. This planar graph needs every one of the colors the Four Color Theorem allows — unlike the bound of , the bound of cannot be lowered to cover every planar graph.
The octahedron — vertices in antipodal pairs , each vertex adjacent to all vertices that are not its own antipode, edges in all — is planar (it is one of the five Platonic solids). Color each antipodal pair alike: ; ; . The only non-edges are the three antipodal pairs themselves, so every edge joins two DIFFERENT pairs, hence different colors — a proper -coloring. And since are pairwise adjacent (none is another's antipode), a triangle. So , even though its degree is larger than the wheel's above.
At the other extreme, the hexagon is planar (just draw it as a plain hexagon) and, being an EVEN cycle, is bipartite (Topic 7), so exactly: alternate colors around the ring. Across these three examples takes the values , , and for planar graphs of similar size; the Four Color Theorem guarantees it can never reach , for ANY planar graph at all.
Forgetting that the Four Color Theorem needs the hypothesis "planar." has (Section 1), already more than — no contradiction, because is NOT planar: it has edges, exceeding the planar bound for vertices. Drop the planarity hypothesis and colors fail for arbitrarily large graphs ( needs all ); the theorem is a genuinely TOPOLOGICAL fact about crossing-free drawings, never a universal cap on .
A planar graph has one vertex of degree . Does the Five Color Theorem still guarantee the WHOLE graph is -colorable?
Show the answerHide the answer
Yes. The planar edge bound only guarantees that SOME vertex has degree at most (the average degree is under ) — not that EVERY vertex does. A single vertex of degree is no obstruction: the inductive proof below finds a DIFFERENT, low-degree vertex elsewhere to remove first, colors the rest of the graph, and only deals with the degree- vertex after everything around it is already settled. **Yes** — the theorem applies to every planar graph, regardless of how high any one vertex's degree happens to be.
Why It Works
Fix any order and run the greedy algorithm with the colors available. When vertex is reached, only its NEIGHBORS can have forbidden its color so far, and has at most neighbors in total (colored or not) — so at most of the available colors are ever forbidden at the moment is colored. At least one color therefore remains free, and greedy assigns it. Since this holds at every step for every vertex, greedy completes a proper coloring using only the colors , regardless of the order chosen. A completed proper coloring with colors exists, so .
Claim: for all . Deleting one edge of leaves the path , and contracting that same edge merges its two endpoints into one vertex, turning the rest of the cycle into ; deletion-contraction gives
Base case : is colored by choosing pairwise-different colors in order, , which equals , matching the claim. Inductive step: assume . Substituting,
using and . This matches the claim for , completing the induction.
By induction on for planar . If , give every vertex its own color. For the inductive step, assume every planar graph with fewer than vertices is -colorable, and let be planar with vertices. By the planar edge bound (Topic 8), , so , which forces some vertex to have . Let , planar with vertices; by induction has a proper -coloring. If , or but its neighbors use at most distinct colors among them, some color is free for and coloring it finishes the job. The remaining case is with neighbors , in their natural cyclic order around in the planar drawing, colored respectively — all five colors used. Let be the subgraph of induced by the vertices colored or . If and lie in different connected components of , swap colors throughout 's component; this keeps the coloring of proper (swapping two colors inside one connected component of a two-color subgraph never creates a same-colored edge, inside the component or crossing its boundary), and now none of 's neighbors is colored , so can take color . Otherwise and lie in the SAME component of , joined by a path alternating colors ; together with the two edges and , this path forms a cycle through . Since sits between and in the cyclic order around while sits on the other side (between and and ), the planar drawing forces this cycle to separate from : any path between them must cross the cycle, and it can only cross through a vertex colored or . So no path from to can alternate purely between colors and , meaning and lie in different components of (the subgraph induced by colors ). Swap colors throughout 's component; this again keeps properly colored, and now none of 's neighbors is colored , so can take color . Either way receives a proper -coloring, completing the induction.