Proving that G must have an area bordered by maximum of 5 edges

40 Views Asked by At

I am working on this proof about planar graphs:

Let G be a planar and connected Graph where every node has a degree higher than or equal to $3$. Show that G must have an area bordered by a maximum of $5$ edges.

I started by a proof by contradiction so assumed that every area gets bordered by a minimum of $6$ edges. I then created the following inequalities: $2 \cdot e \ge 3 \cdot v$ (Handshaking Lemma) and $f \le 1/3 e$. I tried plugging those values into the Eulers polyhedron formula but I am struggling since I don't have much experience with inequalities, especially when it comes to plugging them into equalities. I would appreciate any help! :)

1

There are 1 best solutions below

2
On

$2=v-e+f\le \frac{2e}{3}-e+\frac e3=0$ gives a contradiction.