Inductive Proof of Euler's Formula $v-e+r=2$

Question

I'm just studying for finals here. My professor told me that there would be an inductive proof on the final, and I've never done one before. He told me a good sample problem was to prove Euler's formula $v-e+r=2$ inductively. I've submitted my proof below. I'm just looking for criticism / corrections! Is it a proper inductive proof? If not, could you show me one / make corrections?

Answer 1

Prove that for any connected planar graph $G=(V,E)$ with $e \geq 3$, $v-e+r=2$, where $v = |V|$, $e=|E|$, and $r$ is the number of regions in the graph.

Inductive Hypothesis:

$S(k):$ $v-e+r=2$ for a graph containing $e = k$ edges.

Basis of Induction:

$S(3):$ A graph $G$ with three edges can be represented by one of the following cases:

1. $G$ will have one vertex $x$ and three loops $\{x,x\}$. For this case, $v=1$, $e=3$, $r=4$, and $v-e+r=1-3+4=2$
2. $G$ will have two vertices $x,y$, one edge $\{x,y\}$, and two loops $\{x,x\}$ (or $\{y,y\}$). For this case, $v=2$, $e=3$, $r=3$, and $v-e+r=2-3+3=2$
3. $G$ will have two vertices $x,y$, one edge $\{x,y\}$, one loop $\{x,x\}$ and one loop $\{y,y\}$. For this case, $v=2$, $e=3$, $r=3$, and $v-e+r=2-3+3=2$
4. $G$ will have two vertices $x,y$, two edges $\{x,y\}$ and one loop $\{x,x\}$ (or $\{y,y\}$). For this case, $v=2$, $e=3$, $r=4$, and $v-e+r=2-3+4=2$
5. $G$ will have three vertices $x,y,z$ and three edges: $\{x,y\},\{y,z\},\{z,x\}$. For this case, $v=3, e=3, r=2$ and $v-e+r=3-3+2=2$

Inductive Step:

$S(k+1):$ Assume $S(k)$ to be true. Then for a connected planar graph $G=(V,E)$ with $e\geq3$, $v-e+r=2$. From $S(k)$, move to $S(k+1)$ by adding one edge to $G$. Call this new graph $H$. Let $v', e',$ and $r'$ represent the number of vertices, edges, and regions in $H$, respectively. Now, be created in one of the following ways:

1. Add a loop to some $v \in V$. This divides on region bordering $v$ into two regions. Then, $v'=v, e'=e+1, r'=r+1$, and $v'-e'+r'=v-(e+1)+(r+1)=(v-e+r)-1+1=2$
2. Add an edge $\{x,y\}$ to $E$ for some $x,y \in V, x \neq y$. $x$ and $y$ must border a similar region $t$, or the edge $\{x,y\}$ will violate the planarity of $H$. This new edge will divide region $t$ into two regions. So, $v'=v, e'=e+1, r'=r+1,$ and $v'-e'+r'=v-(e+1)+(r+1)=(v-e+r)-1+1=2$
3. Add an edge $\{x,y\}$ to $E$ and vertex $y$ to $V$ for some $x \in V$, $y \notin V$. $y$ must be added in a region $t$ that borders $x$, or the new edge will violate the planarity of $H$. So, $v'=v+1, e'=e+1, r'=r, and $v'-e'+r'=(v+1)-(e+1)+r=(v-e+r)+1-1=2$