Planar graphs and the Four Color Theorem are key concepts in graph coloring. They explore how graphs can be drawn on a plane without edge crossings and colored using only four colors, connecting geometry and combinatorics in fascinating ways.

These ideas have far-reaching implications, from map coloring to resource allocation. The Four Color Theorem's proof, using computer assistance, sparked debates about mathematical proofs and opened new avenues for exploring graph properties and coloring algorithms.

Planar Graphs and Properties

Definition and Characteristics

• Planar graph drawn on a plane without edge crossings except at vertices
• Euler's formula for planar graphs $v - e + f = 2$ (v vertices, e edges, f faces)
• Maximum edges in a planar graph (n ≥ 3 vertices) $3n - 6$
• Every planar graph contains at least one vertex of degree 5 or less
• Planar graph divides plane into regions called faces including one unbounded external face
• Dual graph of a planar graph forms another planar graph where faces become vertices

Kuratowski's Theorem and Graph Subdivision

• Kuratowski's theorem defines planarity based on absence of specific subgraphs
• Graph is planar if and only if it lacks subgraph that is subdivision of K5 or K3,3
• K5 represents complete graph on 5 vertices
• K3,3 denotes complete bipartite graph on 3+3 vertices
• Subdivision involves inserting vertices along edges without changing graph structure
• Theorem provides method for determining planarity by analyzing subgraph compositions
• Applications in graph theory and network design (computer networks, circuit layouts)

The Four Color Theorem

Statement and Historical Context

• Four Color Theorem states any planar graph colorable using at most four colors
• Adjacent vertices must have different colors
• Francis Guthrie first conjectured theorem in 1852
• Kenneth Appel and Wolfgang Haken proved theorem in 1976 using computer assistance
• Proof sparked controversy due to reliance on computer verification
• Led to discussions about nature of mathematical proofs (human vs. computer-aided)
• Theorem applies to political maps (countries as vertices, shared borders as edges)

Implications and Related Concepts

• Dual graph of map coloring problem represents regions as vertices and adjacency as edges
• Chromatic number of any planar graph at most four due to Four Color Theorem
• Theorem has profound implications in graph theory (vertex coloring, graph partitioning)
• Applications in topology (surface coloring, manifold decomposition)
• Relevance in computer science (resource allocation, scheduling problems)
• Inspired development of new proof techniques (computer-assisted proofs, formal verification)
• Connections to other areas of mathematics (algebraic geometry, combinatorial optimization)

Applying the Four Color Theorem

Graph Analysis and Coloring Process

• Identify planar graph structure recognizing vertices, edges, and faces
• Determine graph planarity by checking for crossing edges or applying Kuratowski's theorem
• Begin coloring process by assigning colors to vertices
• Ensure no two adjacent vertices share same color
• Use systematic approach like greedy coloring algorithm for efficient coloring
• Greedy algorithm assigns lowest-numbered color not used by neighbors
• Consider using Kempe chains to resolve conflicts and rearrange colors
• Kempe chains involve swapping colors between connected components of two colors

Advanced Techniques and Verification

• Utilize concept of reducibility to simplify complex graphs into manageable subgraphs
• Reducibility identifies configurations that can be colored using four colors
• Apply discharge method to analyze local structures and their impact on global coloring
• Implement backtracking algorithms for systematic exploration of coloring possibilities
• Employ heuristics to guide color choices (degree-based ordering, saturation degree)
• Verify final coloring ensuring no more than four colors used
• Check all adjacent vertices have different colors
• Consider computational complexity of coloring algorithms (NP-completeness of graph coloring)

Planar vs Non-planar Graphs

Fundamental Non-planar Graphs

• K5 (complete graph on 5 vertices) fundamental non-planar graph
• K3,3 (complete bipartite graph on 3+3 vertices) another fundamental non-planar graph
• Any graph containing subdivision of K5 or K3,3 non-planar (Kuratowski's theorem)
• Chromatic number of K5 equals 5
• Chromatic number of K3,3 equals 2
• Petersen graph common non-planar graph with chromatic number 3
• Non-planar graphs can have chromatic numbers higher than 4 (unlike planar graphs)

Analysis Techniques for Non-planar Graphs

• Apply concept of graph minors to determine if graph contains K5 or K3,3 as minor
• Graph minor obtained by edge deletions and contractions
• Presence of K5 or K3,3 as minor indicates non-planarity
• Chromatic number of non-planar graph not bounded by Four Color Theorem
• Requires additional analysis to determine chromatic number of non-planar graphs
• Consider graph embedding on higher-genus surfaces (torus, Klein bottle)
• Analyze crossing number to quantify degree of non-planarity
• Explore connections between non-planarity and graph connectivity (edge-connectivity, vertex-connectivity)