11.6 Graph Coloring and Planarity

Sections 11.1–11.5 treated edges as relationships to store, connections to optimize, or routes to follow. Edges can also represent conflicts. If two exams share students, they cannot occur at the same time; if two radio transmitters interfere, they cannot use the same channel.

Graph coloring assigns limited resources without giving adjacent vertices the same resource. Planarity asks a different design question: can all edges be drawn without crossings?

Proper vertex coloring

A vertex coloring assigns a color to every vertex. The coloring is proper when adjacent vertices receive different colors:

where $c(v)$ denotes the color assigned to vertex $v$.

Colors are only labels. They may represent time slots, frequencies, registers, storage bins, or literal colors.

A graph is $k$-colorable if it has a proper coloring using at most $k$ colors. The smallest possible number is the chromatic number, written

An independent set is a set of vertices with no edge between any two of them. Every color class in a proper coloring is an independent set, because vertices sharing a color cannot be adjacent.

For a triangle $K_3$, every pair of vertices is adjacent, so three colors are necessary and sufficient:

Here $K_n$ denotes the complete graph on $n$ vertices, in which every pair of distinct vertices is adjacent.

Lower and upper bounds

A clique is a set of vertices that are pairwise adjacent. If the largest clique has size $r$, its vertices need $r$ different colors, so

This is a lower bound, not always an exact answer.

A simple upper bound comes from a greedy procedure. Choose a vertex order. For each vertex in turn, assign the lowest-numbered color not already used by its colored neighbors.

If the maximum degree is

then at most $\Delta(G)$ neighbor colors can be forbidden when a vertex is processed. Therefore greedy coloring never needs more than

colors.

The result depends on vertex order. A poor order may use more colors than necessary, so a greedy coloring proves an upper bound but does not automatically prove $\chi(G)$.

Bipartite graphs and two colors

A graph is bipartite when its vertices can be divided into disjoint sets $X$ and $Y$ so that every edge has one endpoint in each set. There are no edges within $X$ or within $Y$.

Giving all vertices in $X$ one color and all vertices in $Y$ another proves that every nonempty bipartite graph is $2$-colorable.

Conversely, any proper coloring with two colors divides the vertices into two independent color classes, so the graph is bipartite. Thus

There is also a route test:

To see the forward direction, colors must alternate around every cycle, so returning to the starting color requires an even number of edges. For the reverse direction, run BFS in each component and color even-distance layers one color and odd-distance layers another. An edge within one parity would create an odd cycle.

Schedule a live exam conflict network. Assign time slots directly, observe clashes immediately, reorder the greedy scheduler, reveal clique lower bounds, and switch to a bipartite scenario where BFS layers become a two-color certificate.

Drawings, crossings, and planar graphs

A graph drawing places vertices as points and edges as curves joining their endpoints. Edges may meet at a shared endpoint. A crossing occurs when the interiors of two edges intersect.

A graph is planar if it has at least one drawing with no crossings. A particular crossing-free drawing is called a plane graph.

This distinction matters: a planar graph can be drawn badly with crossings. Moving vertices and rerouting edges may remove them. Conversely, failing to untangle one drawing does not by itself prove that the graph is nonplanar.

A crossing-free drawing divides the plane into regions called faces. The unbounded outside region is also a face.

For every connected plane graph,

This is Euler's formula for planar graphs. It connects the abstract counts of vertices and edges to the number of regions in a crossing-free drawing.

For a tree, $|E|=|V|-1$ and there is one face, the outside face. Substitution gives

so the formula continues the tree facts from Chapter 10.

Edge bounds for simple planar graphs

Let a connected simple planar graph have $n=|V|\ge3$ vertices and $m=|E|$ edges. If every face boundary has at least three edge appearances, then counting edge appearances around faces gives

because every edge borders two face sides. Combining this with $|F|=2-n+m$ yields

This is a necessary condition for simple planar graphs. If a simple graph violates it, the graph is nonplanar. Satisfying the inequality does not prove planarity.

A bipartite graph has no odd cycle, so a simple bipartite plane graph has no triangular face. Every face boundary has at least four edge appearances, giving the stronger bound

Two fundamental nonplanar graphs

The complete graph $K_5$ has

so it is nonplanar.

The complete bipartite graph $K_{r,s}$ has two vertex groups of sizes $r$ and $s$, with every possible edge between the groups and no edge within a group. For $K_{3,3}$,

so the bipartite planar bound proves that $K_{3,3}$ is nonplanar.

The ordinary bound $m\le3n-6$ would not reject $K_{3,3}$, showing why graph structure can strengthen a counting argument.

Certificates and boundaries

To prove that a graph is planar, provide a crossing-free drawing or a precise embedding description. To prove that a graph is nonplanar, an edge-bound violation is sufficient when it applies, but not every nonplanar graph violates the basic bound.

The crossing count belongs to a drawing, while planarity belongs to the graph. A draggable picture can discover an embedding and build intuition, but a mathematical conclusion still needs a certificate: a zero-crossing drawing for planarity, or a valid impossibility argument for nonplanarity.

Drag vertices to untangle straight-line drawings while a geometric scanner identifies each crossing. Compare a planar prism that can reach zero crossings with $K_5$ and $K_{3,3}$ cases whose edge-count certificates block success even as the drawing changes.

Chapter 11 synthesis

Graphs model objects and relationships. Representations turn those models into data; degree counts local incidence; routes define connectivity; BFS, DFS, and Dijkstra explore or optimize paths; spanning-tree algorithms build minimum-cost backbones; Euler and Hamilton problems distinguish edge coverage from vertex coverage; coloring allocates conflicting resources; and planarity constrains drawings through counting.

Section 2.4 already used Boolean algebra to describe immediate decisions. Chapter 12 now adds changing state: finite-state machines will describe controlled transitions, and the final project will combine those ideas with the network models developed here.