I've spent the last 7 hours trying to solve this one problem, no kidding. The textbook is absolutely useless and there's nothing helpful on the internet.
Let $G$ be a simple plane graph with fewer than $12$ faces, in which each vertex has degree at least $3$. Use Euler's formula to prove that $G$ has a face bounded by at most four edges.
Euler's Formula:
$$n – m + f = 2$$
So:
$$f \le 11$$
For every vertex $v$, $deg(v) \ge 3$
So far I've figured out that I should probably prove (the contrapositive) that it's impossible for every face to be bounded by $\ge 5$ edges. In that case, there would be at least $5$ edges, and by extension, at least $5$ vertices. Also, the complete graph $K3$ has $4$ vertices and $8$ edges, so those are also minimums. Also that $5f \le 2m$, since each face is surrounded by $\ge 5$ edges and each edge is surrounded by $2$ faces.
Where do I go from there? I've covered 4 notebook pages in useless equations trying to work something out but have not made any progress at all.
Please help me.
Best Answer
Every edge has two vertices, so the sum of the degrees of all vertices is $2m$. In particular, $2m \ge 3n.$
Therefore, $$2 = n - m + f \le -\frac{1}{3}m + f.$$
Every edge bounds two faces. So the sum of the number of edges bounding each face is also $2m$. If every face were bounded by at least five edges, then $5f \le 2m$. Together with the previous inequality, $$f \ge 2 + \frac{1}{3}m \ge 2 + \frac{5}{6}f,$$ or in other words $f \ge 12.$