Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 0 down vote accepted

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$
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.