0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ So $-e+f=2-v$, but the left side is positive. This doesn't leave very many possibilities for $v$... $\endgroup$ – Casteels Dec 23 '14 at 13:06
  • 3
    $\begingroup$ Also note that if $G$ has $c$ components, then Euler's formula becomes $v-e+f=1+c$. $\endgroup$ – Casteels Dec 23 '14 at 13:11
1
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Some people consider the empty graph to be connected, so they would argue that it should be included in the part of your answer dealing with connected graphs. I don't consider the empty graph to be connected, so as far as I'm concerned it is correctly handled in the part of your answer dealing with disconnected graphs: It's the disjoint union of $0$ flowers. +1 $\endgroup$ – Andreas Blass Aug 1 '17 at 4:29
  • $\begingroup$ @AndreasBlass Yes, that was my thought on the empty graph, too. Part of the reason I defer it to the part on not-connected graphs is because I'm arguing from Euler's formula, and the empty graph must use the extended form $v - e + f = 1 + c$ with $c=0$. I'll make it more explicit that the empty graph counts as well. Thanks! $\endgroup$ – user326210 Aug 1 '17 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.