Let G= (V,E) be an undirected connected loop-free graph.Prove that...

Question

Let G = (V,E) be an undirected connected loop-free graph. Suppose further that G is planar and determines 53 regions. If for some planar embedding of G, each regions has at least 5 edges in its boundary, prove that $|v| \ge 82$.

Answer 1

Hint: there are $53$ regions, each surrounded by at least $5$ edges, so the number of edges is at least $53\times5$. . . except that this is wrong. Work out why, and fix it, and you will be very close to the solution. As you said, you will also need Euler's Theorem.

Answer 2

By "loop free" you mean "no edge joins a vertex to itself," right?

For the plane, and an embedding of a finite conencted graph, $V - E + F = 2$ (where the "outer" region is one face). In your case, $F = 54$ (there are 53 regions, and then the "outside"), so $V - E = -52$, so $V = E - 52$

Now each edge is shared by exactly 2 faces. If we count the number of edges of all the faces (so that each edge is counted twice), we get at least $5F$ edges. So the number of actual edges, nto double counted, is at least $5F/2$, i.e., $$ E \ge 5F/2 = 5 * 54/2 = 135 $$ But we have $$ V = E - 52 \ge 135 - 52 = 83 $$ so the number of vertices is at least 83.

There might be an off-by-one somewhere above, but that's the gist of it.