Planarity and Graph Coloring

Planarity and Coloring

Planar Graphs

A graph is planar if it can be drawn on the plane without any edge crossings.

Euler's formula: For a connected planar graph, $V - E + F = 2$, where $F$ is the number of faces (including the outer face).

Corollary: $E \le 3V - 6$ (for $V \ge 3$). If there are no triangles: $E \le 2V - 4$.

Graph $K_5$ (complete graph on 5 vertices): $E=10$, $3V-6=9$. Therefore, $K_5$ is non-planar.

Graph $K_{3,3}$ (complete bipartite 3+3): $E=9$, $2V-4=8$ (bipartite). Non-planar.

Kuratowski's theorem: A graph is planar if and only if it does not contain a subgraph that is a subdivision of $K_5$ or $K_{3,3}$.

Graph Coloring

The chromatic number $\chi(G)$ is the minimal $k$ such that one can color the vertices with $k$ colors so that adjacent vertices have different colors.

$\chi(G) = 1$ if and only if $G$ is empty (no edges). $\chi(G) = 2$ if and only if $G$ is bipartite.

The Four Color Theorem (Appel, Haken, 1976): Every planar graph has $\chi \le 4$. The first major proof to use a computer (checking 1936 configurations).

Applications: Scheduling (conflicts $\to$ edges), frequency assignment (radio networks), map coloring.

Ramsey’s Theorem

$R(m,n)$ is the smallest $N$ such that any two-color edge coloring of $K_N$ contains a $K_m$ in the first color or a $K_n$ in the second color.

$R(3,3) = 6$: among 6 people, there are always either 3 all mutual acquaintances or 3 all mutual strangers.

Ramsey theory studies "order in chaos" — inevitable patterns in large structures.

Chromatic Polynomial and Algebraic Methods

The chromatic polynomial $P(G, k)$ is the number of proper $k$-colorings of graph $G$. This is a polynomial in $k$ of degree $n$ (number of vertices). For an empty graph (no edges): $P = k^n$. For the complete graph $K_n$: $P = k(k-1)(k-2)...(k-n+1)$. Deletion-contraction recurrence: $P(G, k) = P(G - e, k) - P(G/e, k),$ where $G-e$ is the graph with edge $e$ deleted, $G/e$ is the graph with edge $e$ contracted.

The minimal $k$ with $P(G, k) > 0$ is the chromatic number $\chi(G)$. The Four Color Theorem $\iff P(G, 4) > 0$ for all planar $G$. Computing $P(G, k)$ is a #P-complete problem (harder than NP-complete — counting the number of solutions rather than just determining existence).

Ramsey Theorem: Exact Values

Only a few exact values of Ramsey numbers are known: $R(3,3)=6$, $R(3,4)=9$, $R(3,5)=14$, $R(4,4)=18$. Already $R(5,5)$ is unknown: only $43 \le R(5,5) \le 48$ is known. Computing $R(5,5)$ is one of the open problems in combinatorics. Erdős observed: if an alien civilization demanded the value of $R(5,5)$ under threat of destroying the Earth, all mathematicians should devote their efforts to it. If they demanded $R(6,6)$ — it would be better to try launching a preemptive attack.

Upper bound: $R(m,n) \le C(m+n-2, m-1)$ — from a combinatorial proof via the pigeonhole principle. Lower bound of Erdős–Spencer: $R(n,n) > 2^{n/2}$ (probabilistic method, 1947). This gap between $2^{n/2}$ and $4^n$ reflects our limited knowledge.

Bipartiteness and Bipartite Matching Algorithm

Hall's Theorem (Marriage theorem): A bipartite graph $G=(A \cup B, E)$ has a matching saturating $A$ if and only if for every $S \subseteq A$: $|N(S)| \ge |S|$ ($N(S)$ are the neighbors of $S$). This Hall condition is necessary and sufficient.

The Hopcroft-Karp algorithm finds a maximum matching in a bipartite graph in $O(\sqrt{V} \cdot E)$ — an optimal algorithm. Applications: assignment problem (workers $\leftrightarrow$ tasks with minimal cost — Hungarian algorithm $O(V^3)$), student-project allocation, matching in online advertising (ad slots $\leftrightarrow$ real-time users).

The Five Color Theorem: Constructive Proof

In contrast to the Four Color Theorem, the theorem on five colors for planar graphs has an elegant constructive proof (Kempe, 1879, corrected by Heawood). Idea: by Euler's formula, every planar graph ($V \ge 3$) always has a vertex of degree $\le 5$. Remove it, 5-color the remainder (by induction), and return the vertex. If it has $\le 4$ neighbors — color it with a free color. If its 5 neighbors all have different colors — use the Kempe chain argument to free up a color.

The simplicity of the five-color proof versus the complexity of the four-color proof (computer-verified 1936 cases) illustrates a fundamental difference: sometimes a slightly weaker result allows for an incomparably more elegant proof.

Directed Graphs and Reachability Problems

In a directed graph (digraph), the edges have direction. Strong connectivity: every vertex is reachable from any other. Tarjan's algorithm finds strongly connected components in $O(V+E)$ — a single DFS pass using a stack and discovery numbering. Condensation: the graph of strongly connected components is a DAG (acyclic digraph). The reachability problem in a DAG is solved by topological sorting in $O(V+E)$. Applications: dependency analysis in compilers, detection of cyclic dependencies.

Numerical Example: Strongly Connected Components

Problem: A digraph on 5 vertices: $1 \to 2$, $2 \to 3$, $3 \to 1$, $3 \to 4$, $4 \to 5$, $5 \to 4$. Find the SCCs using Tarjan's algorithm.

Step 1: DFS from 1: discovery numbers $d[1]=0$, $d[2]=1$, $d[3]=2$, $d[4]=3$, $d[5]=4$. Stack: [1,2,3,4,5].

Step 2: At vertex 5: edge $5 \to 4$, $d[4]=3 < d[5]$ $\to$ back edge. $low[5]=\min(4,3)=3$. $d[5]=low[5]$? No $(4 \ne 3)$. Return to 4.

Step 3: At vertex 4: $low[4]=\min(3, low[5])=3$. $d[4]=low[4]=3$ $\to$ pop up to 4: ${\rm SCC}_1 = {4,5}$.

Step 4: Continue: $3 \to 1$ — back edge to $d=0$, $low[3]=0$. Return: $low[2]=0$, $low[1]=0$. $d[1]=low[1]=0$ $\to$ pop: ${\rm SCC}_2 = {1,2,3}$. Condensation is a DAG: ${\rm SCC}_2 \to {\rm SCC}_1$. Thus a compiler detects mutual recursion.