How can I prove Euler's formula using mathematical induction

Question

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.

Answer 1

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.