Admin: Create Chapter 6: Planar Graphs page from study notes (via create-page on MediaWiki MCP Server)

2026-06-14T19:16:10Z

Create Chapter 6: Planar Graphs page from study notes (via create-page on MediaWiki MCP Server)

New page

= Chapter 6: Planar Graphs =

== Overview ==

Chapter 6 of Douglas B. West's ''Introduction to Graph Theory'' (2nd Edition) is devoted to '''planar graphs''' -- graphs that can be drawn in the plane without edge crossings. The chapter is motivated by two classical problems: the Four Color Problem (whether every map on a globe can be colored with four colors so that regions sharing a nontrivial boundary have different colors) and circuit layout design (where wire crossings cause problems in silicon chip layouts). The chapter is organized into three major sections:

# '''Section 6.1: Embeddings and Euler's Formula'''
# '''Section 6.2: Characterization of Planar Graphs'''
# '''Section 6.3: Parameters of Planarity'''

== 6.1 Embeddings and Euler's Formula ==

=== Drawings in the Plane ===

The section opens with the classic "gas-water-electricity" brain teaser (Example 6.1.1): three houses each need paths to three utilities without crossings. This is equivalent to asking whether <math>K_{3,3}</math> can be drawn in the plane without edge crossings -- it cannot.

'''Key Definitions:'''

* '''Proposition 6.1.2:''' <math>K_5</math> and <math>K_{3,3}</math> cannot be drawn without crossings. The proof uses spanning cycles and the impossibility of arranging conflicting chords.
* '''Curve''' (Definition 6.1.3): The image of a continuous map from <math>[0,1]</math> to <math>\mathbb{R}^2</math>. A '''polygonal curve''' is composed of finitely many line segments. A '''drawing''' of a graph <math>G</math> assigns each vertex a point and each edge a polygonal curve between the endpoint images. A '''crossing''' is a non-endpoint intersection of edge images.
* '''Planar graph''' (Definition 6.1.4): A graph that has a drawing without crossings. Such a drawing is called a '''planar embedding'''. A '''plane graph''' is a particular planar embedding of a planar graph.
* '''Open set, region, face''' (Definition 6.1.5): A planar embedding partitions the plane into '''faces''' -- the maximal regions containing no point used in the embedding. There is always one unbounded face, called the '''outer face'''.
* '''Restricted Jordan Curve Theorem''' (Theorem 6.1.6): A simple closed polygonal curve partitions the plane into exactly two faces, each having the curve as boundary. This fundamental topological result underpins many arguments about planar graphs.

=== Dual Graphs ===

* '''Dual graph''' (Definition 6.1.7): Given a plane graph <math>G</math>, the '''dual graph''' <math>G^*</math> has vertices corresponding to the faces of <math>G</math>, and edges corresponding to the edges of <math>G</math> (each dual edge crosses exactly one primal edge, connecting the two faces on either side).
* '''Example 6.1.8:''' The dual of any planar embedding of <math>K_4</math> is another copy of <math>K_4</math>. The dual of the cube <math>Q_3</math> (8 vertices, 12 edges, 6 faces) is <math>K_{2,2,2}</math> (6 vertices, 12 edges, 8 faces). The dual can introduce loops and multiple edges.
* '''Remark 6.1.9:''' A cut-edge in <math>G</math> becomes a loop in <math>G^*</math>. Multiple edges arise when distinct faces share more than one boundary edge. The double dual <math>(G^*)^*</math> is isomorphic to <math>G</math> if and only if <math>G</math> is connected.
* '''Face length''' (Definition 6.1.11): The total length of the closed walk(s) bounding a face. A cut-edge contributes twice to its face's length.
* '''Proposition 6.1.13:''' The sum of all face lengths equals <math>2e(G)</math>. This is the dual analogue of the degree-sum formula.
* '''Theorem 6.1.14:''' Edges in a plane graph form a cycle in <math>G</math> if and only if the corresponding dual edges form a bond (minimal edge cut) in <math>G^*</math>. This establishes a fundamental duality between cycles and cuts.
* '''Remark 6.1.15:''' Deleting a non-cut edge in <math>G</math> corresponds to contracting an edge in <math>G^*</math>, and contracting a non-loop edge in <math>G</math> corresponds to deleting an edge in <math>G^*</math>.

=== Bipartite Planar Graphs and Outerplanarity ===

* '''Theorem 6.1.16:''' For a plane graph <math>G</math>, the following are equivalent: (A) <math>G</math> is bipartite, (B) every face has even length, (C) the dual <math>G^*</math> is Eulerian.
* '''Outerplanar graph''' (Definition 6.1.17): A graph that has an embedding with every vertex on the boundary of the unbounded face. An '''outerplane graph''' is such an embedding.
* '''Proposition 6.1.18:''' The boundary of the outer face of a 2-connected outerplane graph is a spanning cycle.
* '''Proposition 6.1.19:''' <math>K_4</math> and <math>K_{2,3}</math> are planar but not outerplanar.
* '''Proposition 6.1.20:''' Every simple outerplanar graph has a vertex of degree at most 2.

=== Euler's Formula ===

* '''Euler's Formula''' (Theorem 6.1.21, Euler [1758]): If a connected plane graph <math>G</math> has <math>n</math> vertices, <math>e</math> edges, and <math>f</math> faces, then <math>n - e + f = 2</math>. This is the fundamental counting tool for planar graphs. The proof uses induction on <math>n</math>, contracting edges while tracking the vertex, edge, and face counts.
* '''Remark 6.1.22:''' All planar embeddings of a connected graph have the same number of faces. For disconnected plane graphs with <math>k</math> components, the formula generalizes to <math>n - e + f = k + 1</math>.
* '''Theorem 6.1.23 (Edge bound):''' If <math>G</math> is a simple planar graph with at least three vertices, then <math>e(G) \leq 3n(G) - 6</math>. If <math>G</math> is also triangle-free, then <math>e(G) \leq 2n(G) - 4</math>. These bounds follow from Euler's Formula combined with the constraint that every face boundary has length at least 3 (or at least 4 if triangle-free).
* '''Example 6.1.24:''' The nonplanarity of <math>K_5</math> (<math>e = 10 > 9 = 3n - 6</math>) and <math>K_{3,3}</math> (<math>e = 9 > 8 = 2n - 4</math>) follows immediately from Theorem 6.1.23.

=== Maximal Planar Graphs and Triangulations ===

* '''Maximal planar graph''' (Definition 6.1.25): A simple planar graph that is not a spanning subgraph of any other simple planar graph. A '''triangulation''' is a simple plane graph in which every face boundary is a 3-cycle.
* '''Proposition 6.1.26:''' For a simple <math>n</math>-vertex plane graph <math>G</math>, the following are equivalent: (A) <math>G</math> has <math>3n - 6</math> edges, (B) <math>G</math> is a triangulation, (C) <math>G</math> is a maximal plane graph.

=== Embeddings on the Sphere and Regular Polyhedra ===

* '''Remark 6.1.27:''' A graph embeds in the plane if and only if it embeds on a sphere. The two settings are interchangeable via stereographic projection.
* '''Application 6.1.28 (Regular polyhedra / Platonic solids):''' Using Euler's Formula and the degree-sum formula for regular plane graphs (where every vertex has degree <math>k</math> and every face has length <math>l</math>), one derives the constraint <math>(k-2)(l-2) < 4</math>, which restricts <math>k, l \geq 3</math> and <math>k, l \leq 5</math>. This yields exactly five solutions -- the five Platonic solids:

{| class="wikitable"
|-
! <math>(k, l)</math> !! Solid !! Vertices !! Edges !! Faces
|-
| (3, 3) || Tetrahedron || 4 || 6 || 4
|-
| (3, 4) || Cube || 8 || 12 || 6
|-
| (4, 3) || Octahedron || 6 || 12 || 8
|-
| (3, 5) || Dodecahedron || 20 || 30 || 12
|-
| (5, 3) || Icosahedron || 12 || 30 || 20
|}

== 6.2 Characterization of Planar Graphs ==

=== Kuratowski's Theorem ===

The central question of Section 6.2 is: ''which graphs embed in the plane?'' <math>K_5</math> and <math>K_{3,3}</math> are the crucial obstructions, leading to Kuratowski's Theorem.

* '''Kuratowski subgraph''' (Definition 6.2.3): A subgraph of <math>G</math> that is a subdivision of <math>K_5</math> or <math>K_{3,3}</math>. A '''minimal nonplanar graph''' is a nonplanar graph such that every proper subgraph is planar.
* '''Proposition 6.2.1:''' If <math>G</math> has a subgraph that is a subdivision of <math>K_5</math> or <math>K_{3,3}</math>, then <math>G</math> is nonplanar. (Since every subgraph of a planar graph is planar, and subdivisions of nonplanar graphs remain nonplanar.)
* '''Kuratowski's Theorem''' (Theorem 6.2.2, Kuratowski [1930]): '''A graph is planar if and only if it does not contain a subdivision of <math>K_5</math> or <math>K_{3,3}</math>.''' This is one of the most celebrated results in graph theory (a TONCAS -- "The Obvious Necessary Condition is Also Sufficient").

=== Preparation for the Proof ===

The proof of Kuratowski's Theorem proceeds through several structural lemmas:

* '''Lemma 6.2.4:''' If <math>F</math> is the edge set of a face in a planar embedding of <math>G</math>, then <math>G</math> has an embedding with <math>F</math> as the edge set of the unbounded face.
* '''Lemma 6.2.5:''' Every minimal nonplanar graph is 2-connected.
* '''Lemma 6.2.6:''' If <math>S = \{x, y\}</math> is a separating 2-set of a nonplanar graph <math>G</math>, then adding edge <math>xy</math> to some S-lobe yields a nonplanar graph.
* '''Lemma 6.2.7:''' If <math>G</math> is a graph with the fewest edges among all nonplanar graphs without Kuratowski subgraphs, then <math>G</math> is 3-connected.

=== Convex Embeddings and Tutte's Theorem ===

* '''Convex embedding''' (Definition 6.2.8): A planar embedding in which every face boundary is a convex polygon.
* '''Lemma 6.2.9''' (Thomassen [1980]): Every 3-connected graph with at least five vertices has an edge <math>e</math> such that <math>G \cdot e</math> (the contraction) is 3-connected.
* '''Lemma 6.2.10:''' If <math>G</math> has no Kuratowski subgraph, then <math>G \cdot e</math> also has no Kuratowski subgraph.
* '''Tutte's Theorem''' (Theorem 6.2.11, Tutte [1960, 1963]): '''If <math>G</math> is a 3-connected graph with no subdivision of <math>K_5</math> or <math>K_{3,3}</math>, then <math>G</math> has a convex embedding in the plane with no three vertices on a line.''' The proof uses induction on <math>n(G)</math>, contracting an edge to obtain a smaller 3-connected graph, applying the induction hypothesis for a convex embedding, and then carefully restoring the contracted vertex.

Together, Lemmas 6.2.7 and Theorem 6.2.11 imply Kuratowski's Theorem.

=== Fáry's Theorem and Straight-Line Embeddings ===

* '''Fáry's Theorem''' (Wagner [1936], Fáry [1948], Stein [1951]): Every simple planar graph has a planar embedding in which all edges are straight line segments. For 3-connected planar graphs, Tutte's Theorem gives the stronger result that there exists a convex embedding.
* '''Schnyder [1992]''' proved that every <math>n</math>-vertex planar graph has a straight-line embedding on the integer grid <math>[n-1] \times [n-1]</math>.

=== Graph Minors ===

* '''Minor''' (Definition 6.2.12): A graph <math>H</math> is a '''minor''' of <math>G</math> if a copy of <math>H</math> can be obtained from <math>G</math> by deleting and/or contracting edges.
* '''Wagner's Theorem''' (Wagner [1937]): A graph is planar if and only if it has neither <math>K_5</math> nor <math>K_{3,3}</math> as a minor. This is equivalent to Kuratowski's Theorem since, for graphs with maximum degree at most 3, <math>H</math> is a minor if and only if <math>G</math> contains a subdivision of <math>H</math>.
* '''Remark 6.2.13:''' <math>K_5</math> is a minor of the Petersen graph, although the Petersen graph does not contain a subdivision of <math>K_5</math>.

=== Planarity Testing (Optional) ===

* '''H-fragment''' (Definition 6.2.15): When <math>H</math> is a subgraph of <math>G</math>, an H-fragment is either (1) an edge not in <math>H</math> whose endpoints are in <math>H</math>, or (2) a component of <math>G - V(H)</math> together with the edges and vertices connecting it to <math>H</math>.
* '''Conflict graph''' (Definition 6.2.16): Two C-fragments <math>A, B</math> '''conflict''' if they have three common vertices of attachment to <math>C</math> or if there are four vertices in cyclic order on <math>C</math> where <math>v_1, v_3</math> attach to <math>A</math> and <math>v_2, v_4</math> attach to <math>B</math>. The '''conflict graph''' has C-fragments as vertices, with conflicting fragments adjacent.
* '''Tutte's planarity criterion''' (Tutte [1958]): <math>G</math> is planar if and only if the conflict graph of each cycle in <math>G</math> is bipartite.
* '''Linear-time planarity algorithms''' exist due to Hopcroft and Tarjan [1974] and Booth and Luecker [1976].

== 6.3 Parameters of Planarity ==

Section 6.3 addresses quantitative measures of "how far" a graph is from being planar, and explores related structural parameters.

=== Crossing Number ===

* The '''crossing number''' <math>\text{cr}(G)</math> of a graph <math>G</math> is the minimum number of edge crossings in any drawing of <math>G</math> in the plane. A graph is planar if and only if <math>\text{cr}(G) = 0</math>.
* Determining the crossing number is NP-hard in general, but bounds exist for specific graph families. The crossing number of <math>K_n</math> and <math>K_{m,n}</math> have been studied extensively.

=== Thickness ===

* The '''thickness''' <math>t(G)</math> of a graph <math>G</math> is the minimum number of planar subgraphs whose union is <math>G</math>. A graph is planar if and only if <math>t(G) = 1</math>.
* For the complete graph <math>K_n</math>, the thickness is known: <math>t(K_n) = \lfloor n/6 \rfloor + 1</math> for most values of <math>n</math>.

=== Genus ===

* The '''genus''' <math>\gamma(G)</math> of a graph <math>G</math> is the minimum genus of an orientable surface on which <math>G</math> can be embedded without crossings. A graph is planar if and only if <math>\gamma(G) = 0</math>.
* Euler's Formula generalizes to surfaces of genus <math>g</math>: for a connected graph embedded on a surface of genus <math>g</math>, <math>n - e + f = 2 - 2g</math>.
* This yields the edge bound <math>e \leq 3(n - 2 + 2g)</math> for simple graphs on a surface of genus <math>g</math>.

=== Coloring of Planar Graphs ===

* The '''Five Color Theorem:''' Every planar graph is 5-colorable. This can be proved using the fact that every planar graph has a vertex of degree at most 5 (from Euler's Formula) combined with an inductive argument.
* The '''Four Color Theorem''' (Appel and Haken [1977]): Every planar graph is 4-colorable. This was the first major theorem proved with essential computer assistance.
* The connection between coloring faces of a plane graph and coloring vertices of its dual links the Four Color Problem to vertex coloring.

=== Edge Coloring and List Coloring of Planar Graphs ===

* Planar graphs satisfy various results concerning edge coloring and list coloring that exploit their structural constraints (sparsity from Euler's Formula, guaranteed vertices of low degree).

== Summary of Key Results ==

{| class="wikitable"
|-
! Result !! Statement
|-
| '''Euler's Formula''' (6.1.21) || For a connected plane graph: <math>n - e + f = 2</math>
|-
| '''Edge bound''' (6.1.23) || Simple planar graph with <math>n \geq 3</math>: <math>e \leq 3n - 6</math>; triangle-free: <math>e \leq 2n - 4</math>
|-
| '''Kuratowski's Theorem''' (6.2.2) || <math>G</math> is planar iff it contains no subdivision of <math>K_5</math> or <math>K_{3,3}</math>
|-
| '''Tutte's Theorem''' (6.2.11) || 3-connected graph with no <math>K_5</math> or <math>K_{3,3}</math> subdivision has a convex embedding
|-
| '''Fáry's Theorem''' || Every simple planar graph has a straight-line embedding
|-
| '''Wagner's Theorem''' (6.2.12) || <math>G</math> is planar iff it has no <math>K_5</math> or <math>K_{3,3}</math> minor
|-
| '''Five Platonic Solids''' (6.1.28) || The only regular polyhedra correspond to <math>(k,l)</math> pairs satisfying <math>(k-2)(l-2) < 4</math>
|-
| '''Bipartite planarity''' (6.1.16) || Plane graph <math>G</math> is bipartite iff every face has even length iff <math>G^*</math> is Eulerian
|}

== Significance ==

Chapter 6 establishes the foundational theory of planar graphs, one of the most deeply studied classes in graph theory. The results connect topology (Jordan Curve Theorem, surface embeddings), combinatorics (Euler's Formula, counting arguments), and algebra (graph minors, the Robertson–Seymour theorem). Kuratowski's Theorem provides a complete forbidden-subgraph characterization of planarity, while Euler's Formula serves as the workhorse for deriving bounds on edges, proving the existence of low-degree vertices, classifying regular polyhedra, and establishing coloring results. The theory developed here underpins later chapters on graph coloring (the Four Color Theorem) and more advanced topics in topological graph theory.

[[Category:Graph Theory]]
[[Category:Introduction to Graph Theory]]

Introduction to Graph Theory/Planar Graphs - Revision history

Admin: Create Chapter 6: Planar Graphs page from study notes (via create-page on MediaWiki MCP Server)