12.8: Another Characterization for Planar Graphs

Last updated
Save as PDF

Page ID: 48384

Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
Google and Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

We did not pick \(K_5\) and \(K_{3,3}\) as examples because of their application to dog houses or quadrapi shaking hands. We really picked them because they provide another, famous, discrete characterizarion of planar graphs:

Theorem \(\PageIndex{1}\)

(Kuratowski). A graph is not planar if and only if it contains \(K_5\) or \(K_{3,3}\) as a minor.

Definition \(\PageIndex{2}\)

A minor of a graph \(G\) is a graph that can be obtained by repeatedly⁴ deleting vertices, deleting edges, and merging adjacent vertices of \(G\).

For example, Figure 12.16 illustrates why C3 is a minor of the graph in Figure 12.16(a). In fact C3 is a minor of a connected graph G if and only if G is not a tree. The known proofs of Kuratowski’s Theorem 12.8.1 are a little too long to include in an introductory text, so we won’t give one.

Figure 12.16 One method by which the graph in (a) can be reduced to \(C_3\) (f), thereby showing that \(C_3\) is a minor of the graph. The steps are: merging the nodes incident to \(e_1\) (b), deleting \(v_1\) and all edges incident to it (c), deleting \(v_2\) (d), deleting \(e_2\), and deleting \(v_3\) (f).

⁴The three operations can each be performed any number of times in any order.