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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
$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:
$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: