Understanding Proof for e ? 3v – 6 in Planar Graphs – Discrete Mathematics

discrete mathematicsgraph theoryplanar-graphsproof-explanation

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$. The face $F_1$ has side length $7$ Similarly, the following graph has a side length of $4$, even though there are only two edges:enter image description here 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,

Related Question