12.4: Bounding the Number of Edges in a Planar Graph

Last updated
Save as PDF

Page ID: 48380

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

Like Euler’s formula, the following lemmas follow by structural induction directly from Definition 12.2.2.

Lemma 12.4.1. In a planar embedding of a connected graph, each edge occurs once in each of two different faces, or occurs exactly twice in one face.

Lemma 12.4.2. In a planar embedding of a connected graph with at least three vertices, each face is of length at least three.

Combining Lemmas 12.4.1 and 12.4.2 with Euler’s Formula, we can now prove that planar graphs have a limited number of edges:

Theorem \(\PageIndex{3}\)

Suppose a connected planar graph has \(v \geq 3\) vertices and e edges. Then

\[\label{12.4.1.} e \leq 3v - 6.\]

Proof

By definition, a connected graph is planar iff it has a planar embedding. So suppose a connected graph with \(v\) vertices and \(e\) edges has a planar embedding with \(f\) faces. By Lemma 12.4.1, every edge has exactly two occurrences in the face boundaries. So the sum of the lengths of the face boundaries is exactly \(2e\). Also by Lemma 12.4.2, when \(v \geq 3\), each face boundary is of length at least three, so this sum is at least \(3f\). This implies that

\[\label{12.4.2.} 3f \leq 2e.\]

But \(f = e - v + 2\) by Euler’s formula, and substituting into (\(\ref{12.4.2.}\)) gives

\[\begin{aligned} 3(e - v + 2) &\leq 2e \\ e - 3v + 6 &\leq 0 \\ e &\leq 3v - 6 & \blacksquare \end{aligned}\]