Why is Euler's Formula for Planar Graph Not Working Here? 
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?


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.$


