Why is Euler's Formula for Planar Graph Not Working Here?

Question

I have worked out $r(n) = 2^n$, $e(n) = 1 + 3 \times 2^n$, $v(n) = 2\times(2^n - 1) + 4$

The expressions of $r(n)$, $e(n)$, and $v(n)$ are correct and this can be verified with $n = 0, 1, 2, 3\ldots$

But when I calculate $v(n) - e(n) + r(n)$, it does not equal to $2$. What's wrong?

Also, can we derive the relationship between v(n) and e(n) using the sum of degree of vertices?

Answer 1

when I calculate $v(n)−e(n)+r(n)$, it does not equal to $2$. What's wrong?

See Euler's formula for planar graphs :

if a finite, connected, planar graph is drawn in the plane without any edge intersections, and $v$ is the number of vertices, $e$ is the number of edges and $f$ is the number of faces (regions bounded by edges, including the outer, infinitely large region), then :

$v-e+f=2$.

In order to take into account the outer region, the formula for the number of regions $f(n)$ must be:

$f(n)=r(n)+1=2^n+1$,

where $r(n)$ is the number of rectangular regions.

For $n=0$ above, we have : $e(0)=v(0)=4,r(0)=1, f(0)=2$. Thus, it works.

---

We can check it reasoning by induction : at each subdivision of a region with a new line we add one region, two new vertices and three new edges.

Thus, assuming by induction hypoteses that $v(n)-e(n)+f(n)=2$, we have :

$$v(n+1)-e(n+1)+f(n+1)=v(n)+2 - (e(n)+3) + f(n)+1 = v(n)- e(n) + f(n) + 2 - 3 + 1 = v(n)- e(n) + f(n) = 2.$$

---

---

In conclusion, if $f(n)=r(n)+1$, from Euler's formula we have :

$v(n)- e(n) + r(n) = v(n)- e(n) + f(n) - 1 = 2-1=1.$

Answer 2

It looks like you are confused about what is the "outter" region. At step $0$, when you have only one rectangle, there are two faces :

The green one is the "inside", the blue one (that extend indefinitively on the plane) is the "outside". Hence

• If you just want to count the number of rectangles, then indeed $r(n)=2^n$.
• But if you want to count the number of faces in graph term, then you must include the outter face, and your formula should be $f(n)=r(n)+1=2^n+1$, verifying $v(n)-e(n)+f(n)=2$, or $v(n)-e(n)+r(n)=1$