# 12.8: Another Characterization for Planar Graphs

• • Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
• Google and Massachusetts Institute of Technology via MIT OpenCourseWare
$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\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 \|}$$ $$\newcommand{\inner}{\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 \|}$$ $$\newcommand{\inner}{\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 repeatedly4 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).

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

This page titled 12.8: Another Characterization for Planar Graphs is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer (MIT OpenCourseWare) .