Determine all connected regular planar graphs G such that the number of regions in a planar embedding of G equals its order.

I am not sure how to approach this problem. I know the solution involves Euler's identity (n - m + r = 2), and I know it is only a property of connected graphs with planar embeddings. I also realize that n = r in this situation. Any ideas on how to approach this?


closed as off-topic by Did, Claude Leibovici, Leucippus, Henrik, choco_addicted Sep 30 '17 at 12:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Did, Claude Leibovici, Leucippus, Henrik, choco_addicted
If this question can be reworded to fit the rules in the help center, please edit the question.


Let $G$ be a $r$-regular planar graph of order $v$ with $e\ge v-1$ edges and $f=v$ faces. Then $r\ge2$ and

$$v-e+f=2 \iff 2v-e=2 \iff 2v-\frac{vr}{2}=2 \iff v(4-r)=4.$$

Since $v$ is a positive integer, we require $4-r$ to be a positive integer as well. Thus the only possibilities are when $r=2,$ or $3.$

When $r=2$, then we have a cycle, which is planar with $2$ regions, but $K_3$ is the smallest cycle and has order $3$, so this is impossible.

The only remaining possibility is when $r=3$ and we observe that $K_4$ is the only $3$-regular graph of order $4$ that also has $4$ regions.


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