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

Solution 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,

Solution 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).