Induction over 2 variables possible? Application: Graph Theory Is it possible to run induction over two variables? For example:
For i=1 to n
 For j=0 to m
 Prove statement P[n=0,m=1] Induction start
Then make two Inductive steps: 
$P[n,m+1],P[n+1,m+1]$
Or maybe I need to make the inductive steps like this: $P[n,m+1],P[n+1,m+n+1]$ since adding one vertex could add $n$ edges at maximum. 
Or maybe it's not possible at all? 
I would like to run induction on a graph, $n$ are vertices and $m$ are edges.
Could this work? If you happen to know a book where they do it. Or maybe an example. 
I have an example of what I would like to prove:
Corollary: In any graph, the number of points of odd degree is even. 
Here I would like to apply induction. I could add an edge to the existing graph but I could also add a new vertex and connect it. 
 A: One way to prove such a statement would be to let $n$ be arbitrary and then prove $P[n,m]$ with induction on $m$. (Or let $m$ be arbitrary and prove $P[n,m]$ with induction on $n$.) This shows that $P[n,m]$ is true for every $n$ and every $m$ either way you do it.
A: The traditional inductive proof is often thought of as a series of domino stones: you push the one at the beginning, and then they all fall, and you know it is all, because they all exist somewhere along this one long (possibly infinite) line.
This idea can easily be generalized for more dimensions. If all objects for which you want to prove something exist somewhere in a (possibly infinite) 2-dimensional array, then you can be assured that they all eventually fall if you can push over the 'first' element (typically $(0,0)$), and if you can show that whenever $(m,n)$ 'falls', then both $(m,n+1)$ and $(m+1,n)$ 'fall' as well ... you can totally imagine how this translates into a diagonal 'rippling, through the whole array, thereby proving it for any $(m,n)$.
So yes, you can indeed do induction on two or three or more variables at the same time ... no need to do one inside the other.
Moreover, you can also generalize strong induction this way: If you cN show that $(m,n)$ 'falls' whenever all $(m',n')$ 'fall' with $m' \le m$ and $n' \le n$ and either $n' < n$ or $m' <m$, then it will be true that all $(m,n)$ fall.
YOu will need the 2-dimensional variant of strong induction to prove your corollary: Every graph with $m$ vertices and $n$ edges has an even number of vertices with an odd degree.
Weak induction won't work, since when you have some arbitrary graph with $m+1$ Vertices and $n$ edges, there is no guarantee that you can remove a vertex without removing some edges.
Base: $m=n=0$ the Null graph has $0$ and thus an even number of vertices with odd degree.
Step: Take arbitrary $m$ and $n$ and let $G$ be a graph with $m$ vertices and $n$ edges.
If $n=0$, then $m>0$, so remove any arbitrary vertex from $G$ to obtain $G'$ With $m'$ vertices and $n'$ edges. Since we had that $n=0$, the removal of the vertex did not remove any edges, so $n'=n=0$. And of course $m'=m-1$. The inductive hypothesis applies to $G'$, so $G'$ has an even number of vertices with odd degree, but that obviously means the original graph $G$ has an even number of vertices with odd degree as well.
IF $n>0$, then remove one edge to ontain $G'$ with $n'=n-1$ edges and $m'=m$ vertices. So, the inductive hypothesis applies to $G'$ meaning it has an even number of nodes with odd degree. However, that means that the original graph has an even number of vertices with odd degree as well, since if the removed edge was between two vertices that both have an even degree in the resulting graph, then in the original graph they both have odd degree, meaning that the number of vertices with odd degree is still even, and [and now do the other cases: both odd degree, and one even and one odd .... you also may want to consider an edge from one vertex to itself].
A: Induction on two variables is fairly common.  The general structure is to nest one induction proof inside another.  For example, in order to prove a statement $P[m,n]$ is true for all $m,n \in \mathbb{N}$, one might proceed as follows:
Induction on $n$:  Base Case, $n = 0$
We need to prove $P[m,0]$.  To do this, we have a sub-proof by induction on $m$:
Induction on $m$:  Base case, $m = 0$
We prove that $P[0,0]$ is true.
Induction on $m$:  Inductive step.
We prove that if $P[m,0]$ is true, then $P[m+1,0]$ is true as well.
This concludes the subproof, which establishes the $n=0$ case for the main argument.
Induction on $n$:  Inductive step
We need to prove that $P[m, n] \implies P[m, n+1]$.  To do this, we will have another sub-proof by induction on $m$:
Induction on $m$:  Base case, $m = 0$
We prove that $P[0, n] \implies P[0, n+1]$.
Induction on $m$:  Inductive step.
We prove that if $P[m, n] \implies P[m, n+1]$, then also $P[m+1, n] \implies P[m+1, n+1]$.
This concludes the subproof, which establishes the inductive step for the main argument, which concludes the main proof as well.
