How can I prove Euler's formula using mathematical induction

Using Euler's formula in graph theory where

$$r - e + v = 2$$

I can simply do induction on the edges where the base case is a single edge and the result will be 2 vertices. A single edge also has only one region which is the external region.

$$r - 1 + v = 2$$

$$1 - 1 + v = 2$$

$$v = 2$$

Which is true if I drew a connected graph of that has a single edge there are two vertices. However, the inductive step where I am supposed to prove that there are $$e + 1$$ edges I am confused on how to prove this. I can simply add another edge and the formula will still stand true but I don't think that's the correct way to do it. For example, I don't think my professor would accept this on the exam if I tried doing the inductive step like this:

$$r - e + v = 2$$

$$1 - (e + 1) + v = 2$$

if we let $$e=1$$ again then there would be

$$1 - 2 + v = 2$$

$$v = 3$$

which is true, a connected graph of two edges has 3 vertices at most. However, i do not think this is the correct way to prove Euler's formula during the inductive step.

• You also have to consider the number of faces. – Peter Mar 18 at 9:52
• Well if we have at most 2 edges there is only one face and that is the external region, but if I remember correctly there should be a formula that correlates the amount of faces to edges. For larger numbers, I could simply plug in that formula into Euler's and then solve. But that might be excessive... – Code4life Mar 18 at 9:55
• See Euler characteristic for Plane graphs : the base case is $2$ faces, that needs $3$ vert and $3$ edges. Thus : $v-e+f=3-3+2=2$. – Mauro ALLEGRANZA Mar 18 at 9:59
• Then to close the induction, you have to prove that any change to the graph that creates an additional face while keeping the graph planar does not change to number. – Mauro ALLEGRANZA Mar 18 at 10:00
• So I should do the induction on the number of faces rather than the number of vertices or edges? Should I just do $r+1$ in Euler's formula? How would I go about doing the inductive step then? – Code4life Mar 18 at 11:10

Let $$v$$ be the number of vertices, $$e$$ the number of edges and $$r$$ the number of regions in a connected simple planar graph $$G$$. To prove Euler's formula $$v - e + r = 2$$ by induction on the number of edges $$e$$, we can start with the base case: $$e = 0$$. Then because $$G$$ is connected, it has a single vertex, so we have $$1 - 0 + 1 = 2$$ and formula holds.

Now suppose the formula holds for all graphs with no more than $$e - 1$$ edges. Let $$G$$ be a graph with $$e$$ edges. Consider two cases. Case 1: G does not contain a cycle. Then G is a tree, for example It has only $$r = 1$$ region and because it is connected, it has $$v - 1$$ edges, so we have $$v - (v - 1) + 1 = 2$$ and formula holds.

Case 2: G contains at least one cycle $$C$$. Remove an edge $$p$$ from the cycle $$C$$ to get a path $$P$$, for example: Cycle $$C$$ separates the plane in two regions. When we remove the edge $$p$$ from $$G$$, we create a new graph $$G'$$, where we merge these two regions. So $$G'$$ has by construction one less region than $$G$$ $$r' = r - 1,$$ the same number of vertices $$v'=v$$ and one less edge than $$G$$ $$e' = e - 1,$$ so induction hypothesis holds and we have $$v - (e - 1) + (r - 1) = 2$$ and from this also $$v - e + r = 2,$$ what we needed to prove. More about Euler's formula is here. Formula can easily be generalized for disconnected graphs or graphs with loops or parallel edges.