Finding all planar graphs with more regions than edges.

Question

I want to find all planar graphs with more regions than edges.

This is my solution. Let $G=(V,E)$ be a planar graph and pick a planar representation.

If $G$ is connected, I can use Euler's formula. This yields $v-e+f=2$. Now we have $f>e$.

How do I continue from here?

And what if $G$ is not connected?

Answer 1

The answer depends on whether you consider the unbounded region outside of a planar graph to be a face, as Euler's formula does. If you do, then the answer is that graphs with this property consist of zero or more "flower-shaped" connected components each with one vertex and with only loops as edges. (See below for proof.)

For example, a single vertex has this property, because it has $v=1$, $e=0$, and $f=1$. Each loop you add to this vertex adds a new face and increases the number of edges by one, preserving the $e < f$ property. Any union of graphs of this kind similarly has this property, and these are the only graphs with this property.

Proof. For any connected planar graph, Euler's formula gives $v - e + f = 2$. To write it another way,

$$v = 2 + e - f$$

If furthermore we want $f > e$, this implies that $e-f$ must be strictly negative, and so $v = 2 + e -f < 2 + 0 = 2$. That is, in order to have more faces than edges in a planar connected graph, we must have $v<2$ (!). The number of vertices $v$ is an integer, and so in particular we must have $v=0$ or $v=1$. In order to have any face at all, though, we must certainly require $v=1$.

This restricts the connected planar graph possibilities to a single vertex, possibly with some loopy (self-directed) edges as these are the only kinds of edges possible. Note that a single vertex with any number of loops has the property required: a single vertex has $v=1$, $e=0$, and $f=1$ (the exterior face). Adding a loop increases the number of faces and edges by one, preserving the $e<f$ property.

Note that this property is only barely attainable, in the sense that for all graphs with this property $e < f$ only because $f - e = 1$.

This has two important implications:

1. If you instead consider only bounded regions to be faces, then there are no graphs with the property that $e > f$. Indeed, in that case we lose our slim margin $f - e = 1$ and the best we can get is $f - e = 0$.
2. To extend our result to planar graphs which are not connected, each connected component must certainly be one of these "flower-shaped" graphs, nothing else. To see this, suppose you start with a flower-shaped graph with $v=1$ and with a certain number of edges $e$ and faces $f = e + 1$. If you add another connected component graph with $v^\prime$ vertices, $e^\prime$ edges, and $f^\prime$ faces, the new number of vertices, edges, and faces becomes $V = v + v^\prime$, $E = e + e^\prime$, and $F = f+f^\prime-1$ (subtracting one so as to avoid counting the exterior region twice). Hence starting with $e < f$, the only way we can have $E < F$ in the graph with more components is if $e^\prime < f^\prime$, which means that the new component must be a flower-shaped graph with $f^\prime = e^\prime + 1$. Hence the new graph will have the same property, $F = E + 1$, and so on as we add more connected components.