Let G be a 3-regular plane graph with 12 faces. How many vertices does G have?

Question

This would be pretty easy to solve if I knew that G is connected by using Eulers formula $|V| - |E| + |F| = 2$.

But I don't know how to show that G is connected. Am I on the wrong path? Or is there some combinatorial argument to count the vertices?

Answer 1

Without the assumption that $G$ is connected, there are simply multiple solutions. You've probably already solved the connected case. But we can also:

• Take a graph with two connected components: a cube graph (with $5$ bounded faces) and a pentagonal prism (with $6$ bounded faces). The result has $11$ bounded faces: $12$ total. There are $18$ vertices.
• Take a graph with three connected components: two tetrahedra and a triangular prism. The result has $3+3+4$ bounded faces, and again $12$ faces total. There are $16$ vertices.

In general, we can generalize Euler's formula to $$ |V| - |E| + |F| = |C|+1 $$ where $|C|$ is the number of connected components. The logic is this: we can add $|C|-1$ edges to the graph to connect the components, getting a connected graph with $|E|+|C|-1$ edges, but the same number of vertices and faces. Applying Euler's formula to the new graph gives us the generalized formula above.

In the general formula, you will not be able to solve for $|V|$, but you will get a relationship between $|V|$ and $|C|$. We also have the inequality $1 \le |C| \le \frac14|V|$: there is always at least one component, and at most $\frac14|V|$ because the smallest $3$-regular planar graph has $4$ vertices. This gives us a range of possibilities for $|V|$ and $|C|$.