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?
Best Answer
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,