12.5: Returning to K5 and K3,3

Last updated
Save as PDF

Page ID: 48381

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}}\)

Finally we have a simple way to answer the quadrapi question at the beginning of this chapter: the five quadrapi can’t all shake hands without crossing. The reason is that we know the quadrupi question is the same as asking whether a complete graph \(K_5\) is planar, and Theorem 12.4.3 has the immediate:

Corollary 12.5.1. \(K_5\) is not planar.

Proof. \(K_5\) is connected and has 5 vertices and 10 edges. But since \(10 > 3 \cdot 5 - 6\), \(K_5\) does not satisfy the inequality (12.4.1.) that holds in all planar graphs.\(\quad \blacksquare\)

We can also use Euler’s Formula to show that \(K_{3,3}\) is not planar. The proof is similar to that of Theorem 12.4.1. except that we use the additional fact that \(K_{3,3}\) is a bipartite graph.

Lemma 12.5.2. In a planar embedding of a connected bipartite graph with at least 3 vertices, each face has length at least 4.

Proof. By Lemma 12.4.2, every face of a planar embedding of the graph has length at least 3. But by Lemma 11.7.2 and Theorem 11.9.3.3, a bipartite graph can’t have odd length closed walks. Since the faces of a planar embedding are closed walks, there can’t be any faces of length 3 in a bipartite embedding. So every face must have length at least 4. \(\quad \blacksquare\)

Theorem 12.5.3. Suppose a connected bipartite graph with \(v \geq 3\) vertices and \(e\) edges is planar. Then

\[\label{12.5.1.} e \leq 2v - 4.\]

Proof. Lemma 12.5.2. implies that all the faces of an embedding of the graph have length at least 4. Now arguing as in the proof of Theorem 12.4.3, we find that the sum of the lengths of the face boundaries is exactly \(2e\) and at least \(4f\). Hence,

\[\label{12.5.2.} 4f \leq 2e\]

for any embedding of a planar bipartite graph. By Euler’s theorem, \(f = 2 - v + e\). Substituting \(2 - v + e\) for \(f\) in (\(\ref{12.5.2.}\)), we have

\[\nonumber 4(2 - v + e) \leq 2e,\]

which simplies to (\(\ref{12.5.1.}\)). \(\quad \blacksquare\)

Corollary 12.5.4. \(K_{3,3}\) is not planar.

Proof. \(K_{3,3}\) is connected, bipartite and has 6 vertices and 9 edges. But since \(9 > 2 \cdot 6 - 4\), \(K_{3,3}\) does not satisfy the inequality (12.4.1.) that holds in all bipartite planar graphs. \(\quad \blacksquare\)