Understanding proof for $e \leq 3v - 6$ in planar graphs

Question

I have a proof for a property of a planar graph:

Lemma 5.8.4. In a planar embedding of a connected graph, each edge is traversed once by each of two different faces, or is traversed exactly twice by one face.

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

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

$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 5.8.4, every edge is traversed exactly twice by the face boundaries. So the sum of the lengths of the face boundaries is exactly 2e. Also by Lemma 5.8.5, when $v\geq 3$, each face boundary is of length at least three, so this sum is at least $3f$ . This implies that

$3f\leq 2e$

But $f = e - v + 2$ by Euler’s formula, and substituting into the above gives

$3(e - v + 2) \leq 2e$

$= e - 3v + 6 \leq 2e$

$= e \leq 3v - 6$

(Source)

I have been trying to wrap my head around this, but I don't really get it fully. My main issues are:

• Why do we start with $v\geq 3$? Because 3 is the minimum number of vertices needed to forma planar embedding with more than 1 face, or what's the reason?

• I'm also stuck on this:

By Lemma 5.8.4, every edge is traversed exactly twice by the face boundaries. So the sum of the lengths of the face boundaries is exactly 2e. Also by Lemma 5.8.5, when $v\geq 3$, each face boundary is of length at least three, so this sum is at least $3f$ . This implies that

$3f\leq 2e$

Why do the two lemmas imply that $3f$ is lower or equal to $2e$? I understand each lemma on it's own, but I dont follow that conclusion, to be honest.

What is also the significance of this? From what I get, this formula gives an upper-bound on the number of edges in a planar graph, it's then used to proof that a graph is planar nor not, depending on the number of edges, is that right?

Answer 1

First, the reason for $v\geq3$ is that the result would be messier and there are no interesting graphs with 2 or fewer vertices. I think you are missing the significance of the fact that the side length of a face is greater than or equal to $3$. This is because side length counts edges twice if they are traversed twice when moving around the perimeter of the face. For example, the face $F_1$ has a side length of $7$. Similarly, the following graph has a side length of $4$, even though there are only two edges: Combining this with the fact that each edge is traversed twice by faces (either two different faces, or the same face twice), we have a relation between faces and edges in a planar graph. Namely, if we sum the lengths of each face, we know we count each edge twice, thus this sum is precisely $2e$. The least number of edges a face can have is three, so the smallest the sum of the length of each face can be is $3f$. So, $3f$ is also the smallest the value $2e$ can be, since this is the same as the sum of the side lengths of the faces. Thus $$3f\leq 2e$$.

The significance of all this is that we now have a way to show that a given graph is not planar. For example the complete graph on $5$ vertices is not planar since we have $4+3+2+1=10$ edges and $5$ vertices so that we have $3v-6=15-6=9$ which is less than $10$, the number of edges. Also this captures something intuitive about planar graphs, things go wrong when one has too many edges for the number of vertices,

Answer 2

A maximal planar (or triangulated) graph is a simple planar graph that can have no more edges added to it without making it non-planar. All the faces of a maximal planar graph will be triangular (bounded by exactly three edges).

(Note: Any non-maximal planar graph can be made into a maximal planar graph by adding edges between two non-adjacent vertices bounding the same face to bisect that face until all the faces are triangular and no further bisections are possible.)

Since each face of a maximal-planar graph is bounded by exactly 3 edges and each edge will be on the boundary of exactly two faces then:

\begin{align} 3F = 2E \end{align}

Substituting this into the Euler Characteristic (where, for an 2D plane, $\chi\left(g\right)=2$) then the number of edges in a maximal-planar graph is given by:

\begin{align} V &= 2 + E - F \\ V &= 2 + E - \frac{2E}{3} \\ 3V &= 6 + E \\ 3V - 6 &= E \\ \end{align}

Since any planar graph must have equal to or fewer edges than a maximal planar graph with the same number of vertices then all planar graphs must have:

\begin{align} E \le 3V - 6 \end{align}

However, you can also get the the same solution noting that if the graph is not maximal planar then the average number of edges per face will be greater than 3 so:

\begin{align} 3F \le 2E \end{align}

Then substituting this gives:

\begin{align} V & = 2 + E - F \\ V & \ge 2 + E - \frac{2E}{3} \\ 3V &\ge 6 + E \\ 3V - 6 &\ge E \\ \end{align}

What is also the significance of this? From what I get, this formula gives an upper-bound on the number of edges in a planar graph, it's then used to proof that a graph is planar nor not, depending on the number of edges, is that right?

This cannot prove that a simple graph is planar (for example: $K_{(3,3)}$ has 6 vertices and 9 edges, so $E \le 3V - 6$ is true but the graph is actually non-planar) but it can give an easy calculation to demonstrate that a simple graph is non-planar (for example: $K_5$ has 5 vertices and 10 edges so $E \le 3V - 6$ is false and cannot be planar).

Answer 3

The proof is rather straightforward once you have discovered another property, which is that, for a planar graph $G = (V, E)$, $3f \leq 2|E|$ where $f$ is the number of faces in the planar drawing of $G$. A proof of this inequality can be found here:

https://math.stackexchange.com/questions/3897815/what-is-the-definition-of-faces-in-graph-theory-why-does-3f≤2e-hold-for-any-c/4517140#4517140

The rest of this proof can be accomplished algebraically as follows:

By Euler's formula, $f = 2 - |V| + |E|$. Thus, \begin{align*} 3f = 6 - 3|V| + 3|E| &\leq 2|E| \\ 3|E| - 2|E| &\leq 3|V| - 6 \\ |E| &\leq 3|V| - 6 \: \end{align*}