# Planar graph, number of faces, minimum vertex degree 3

In a finite connected planar graph $$G$$, such that $$\delta(G)\geq 3$$, show that at least $$2$$ faces have at most $$5$$ edges. I have tried writing out degree sum from Handshaking lemma and then substituting in Euler's formula but I am stuck there.

• Shouldn't it be at least 4 faces? Commented Jan 16, 2020 at 11:42
• No, i just checked the exercise, its says what I wrote in question. Commented Jan 16, 2020 at 11:53

Using the fact $$\delta(G)\geq 3$$, one could prove each edge is part of a cycle, and therefore bound exactly two faces.

Denote by $$e,v,f$$ the number of edges, vertices and faces in $$G$$ respectively.

## Intuition

Since the proof is quite technical, I'll try to sum up the proposition I use:

1. $$(f-1)\leq \frac{e}{3}$$
2. $$2e\geq 3v$$ which implies $$v-\frac{2e}{3}\leq 0$$
3. Euler formula $$v-e+f=2$$

## Proof

Now assume by contradiction the statement is false, and therefore at least $$f-1$$ of the faces have at least $$6$$ edges.
This implies: $$2e=\sum\limits_{i=1}^{f} \text{#edges of the face } f_i\geq 6(f-1)\implies \\ 2e\geq 6(f-1)\implies (f-1)\leq \frac{e}{3}$$

Using Euler formula $$v-e+f = 2$$, we get $$2 = v-e+f\leq v-e+\frac{e}{3} +1=v-\frac{2e}{3} + 1$$

Since

$$2e = \sum\limits_{u\in V(G)}deg(u) \geq 3v\implies \frac{2e}{3}\geq v$$

and finaly we get a contradiction: $$v-\frac{2e}{3}\leq 0 \implies v-\frac{2e}{3} + 1 \leq 1$$ and because $$v-e+f \leq v-\frac{2e}{3} + 1$$ we get
$$2 = v-e+f \leq 1$$