Planar Graph - Proof

Question

If graph G is a planar graph with less than 30 edges: $|E| \lt 30$, prove that the minimum degree in G is: $δ(G) \le 4$.

I was thinking to somehow combine:

• if graph is planar $\Rightarrow |E| \le 3* |V| - 6$
• $2 * |E| =$ sum of degrees in G

Answer 1

Indeed, if $\delta(G)\ge 5$, then $$ \tag12|E|=\sum_{v\in V}\rho(v)\ge \delta(G)|V|\ge 5|V|$$ combined with $$\tag2 3|V|-6\ge |E|$$ gives us $3(1)+5(2)$: $$6|E|+15|V|-30\ge 15|V|+5|E|$$ or after cancellation,$$|E|\ge 30. $$

Answer 2

Let's $\delta(G) = 5$, then $5|V| \le 2|E|$. Since $G$ is planar, $3|F| \le 2|E|$. So by Euler's formula we have $$ 2 = |V|-|E|+|F| \le \frac{|E|}{15}, $$ which implies $|E| \ge 30$.