Let $n\geq 3$. Is there a connected, planar, bipartite graph with $n$ regions and $n$ vertices?

51 Views Asked by At

The answer given is that according to a Corollary of Euler’s formula (Corollary 3 Section 10.7), such a graph has at most $2n − 4$ edges. Applying this to Euler’s formula ($r = m − n + 2$), there are at most $r = 2n − 4 − n + 2 = n − 2$ regions. My question is, when do we use $m ≤ 2n-4$ and $m ≤ 3n-6$? Why can we not use the second formula here? (Here, $m$ refers to edges and $n$ refers to vertices.)