Understanding proof for $e \leq 3v - 6$ in planar graphs 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?
 A: 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,
A: 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).
A: 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*}
