# 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?

• The four original vertices have degree 2, while all vertices added in subsequent stages have degree 3. Hence $$2\cdot4+3\cdot(v(n)-4)=2e(n).$$ Commented Nov 29, 2019 at 10:31

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

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

• Yeah but it is not working. e(2) = 13, v(2) = 10, r(2) = 2^2 = 4. Then, 13 - 10 + 4 = 1. Commented Nov 29, 2019 at 9:30
• So the expression of r(n) should be 2^n + 1 since it counts the outer region too? Also, I don't get how is r(0) = 2? It should be 1 unless you're double counting. Commented Nov 29, 2019 at 9:35
• This is really confusing. The inner region and the outer one is exactly the same rectangle, so why do we count it twice? Is this just convention? Commented Nov 29, 2019 at 9:44
• @YolandaHui - in what sense the inner and the outer are the "same rectangle" ? The inner is the "area" inside the reactangualr perimeter, while the oter is the infinite area outside the perimeter. You have to consider the "regions"; the rectangualr perimeter is made by the edges and the vertices. Commented Nov 29, 2019 at 9:53
• Can we derive the relationship of v(n) and e(n) in here using the sum of degree of vertices? Commented Nov 29, 2019 at 10:05

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$$
• Apparently, it can be shown that e(n) = e(n−1) + 3 r(n−1) which means your expression of r(n) is wrong? e(1) = e(0) + 3 r(0) = 10. But at step 1, there are only 7 edges not 10. Commented Nov 29, 2019 at 10:24
• That's the case only if you define $r(n)$ to be the number of rectangles. If you define $r(n)$ to be the number of faces, you need to re-write your induction formulas. Commented Nov 29, 2019 at 10:28
• Euler's formula deals with faces,not rectangles Commented Nov 29, 2019 at 10:28
• r(n) is defined as the number of non-overlapping rectangular regions partitioning the initial rectangle at step n. Commented Nov 29, 2019 at 10:29
• yes because the number of faces, let's call it $f(n)$ can be valued as $f(n)=r(n)+1$. Euler's formula yields $v(n)-e(n)+f(n)=2$, therefore $v(n)-e(n)+r(n)=1$ Commented Nov 29, 2019 at 10:33