Planar Graphs and Coloring

A planar graph is simply one you can draw on a flat sheet of paper without any lines crossing; "planar" just means it fits in a plane. Coloring a graph means giving each dot a color so that no two connected dots match. That's good for scheduling, since connected dots are things that clash, like exams sharing students, and colors are time slots. The formula $V - E + F = 2$ is three counts: $V$ (dots), $E$ (lines) and $F$ (faces, the regions the lines cut the paper into, including the big one outside). And $\chi(G) \le 4$ says the fewest colors you need, $\chi(G)$, is never more than 4 for a flat drawing. Two short facts with a lot packed into them.

Euler's formula. For any connected planar drawing, $V - E + F = 2$. A cube's skeleton has $8 - 12 + 6 = 2$. Why should that always come out the same? Build the drawing up one edge at a time and watch $V - E + F$. A single vertex has $1 - 0 + 1 = 2$, since the whole page is one face. Adding a new vertex on the end of a new edge raises $V$ and $E$ together, so nothing changes. Adding an edge between two vertices you already have splits a face in two, raising $E$ and $F$ together, so again nothing changes. Every connected drawing can be built this way, so it's stuck at 2. That's the heart of the proof.

Consequences. Each face of a simple planar graph has at least 3 edges and each edge borders at most 2 faces, which gives $E \le 3V - 6$. In other words, a flat drawing can't hold too many edges. So $K_5$ ($V = 5$, $E = 10 > 9$) is not planar. A similar count shows $K_{3,3}$ isn't either. By Kuratowski's theorem, these two are the only obstacles: a graph is non-planar exactly when it contains a copy of one of them, possibly with extra vertices sitting along its edges.

Coloring. The chromatic number $\chi(G)$ is the fewest colors so adjacent vertices differ. A cycle needs 2 colors if it's even, because you can just alternate. If it's odd, alternating breaks when you get back around, so it needs 3. $K_n$ needs $n$, since every vertex touches every other. A greedy algorithm (color vertices one at a time with the first color available) never needs more than one more than the largest degree, because each vertex has at most that many neighbors blocking colors.

The four color theorem (1976) says every planar graph, and so every map, can be colored with four colors. To see why maps count, put a vertex in each country and join two when they share a border; that graph is planar. It was the first major theorem proved with essential computer help.

A common mistake. It's tempting to apply $E \le 3V - 6$ in reverse and decide a graph is planar because it passes. It doesn't work that way. The inequality can only rule planarity out. $K_{3,3}$ has 9 edges and 6 vertices, well under $3 \cdot 6 - 6 = 12$, and it still isn't planar.

Exam timetables, radio frequency assignments and register allocation in compilers are all graph-coloring problems.