Induction in proofs about graphs It is often the case that proofs of graph-related claims where there's two parameters, (like number of edges and number of vertices) use a type of induction I'm not familiar with. My question is twofold:

*

*Why is this type of induction the right technique?

*E.g., a theorem by Mader says that if the average degree of a graph G is at least $2^{t-2}$, then G has a $t$-clique minor. This is proven using induction on $t+V(G)$. To me this feels quite arbitrary: why this, rather than separate inductions on both $t$ and the number of vertices? Why can we just use induction on the sum of the relevant parameters?

 A: Induction on a quantity like $t + |V(G)|$ or $|V(G)|+|E(G)|$ is always somewhat artificial. To see where it comes from, we first have to take a step back and think about how induction works in general.

The normal setup for an induction proof is to start with $P(0)$ and then prove that $P(n) \implies P(n+1)$. Even with one parameter, you can have other, stranger approaches:

*

*Cauchy induction, which starts with $P(2)$ and then proves $P(n) \implies P(2n)$ and $P(n) \implies P(n-1)$. This is used, for instance, in some proofs of the AM-GM inequality.

*Laplace's proof of the fundamental theorem of algebra, which starts with $P(n)$ for all odd $n$ and then proves $P(\binom n2) \implies P(n)$. (More on this later.)
Arbitrarily strange approaches to induction are fine, as long as they satisfy one fundamental property: for every case of the theorem, there is a finite path of induction steps leading to it from some base case.
With strong induction, you might use multiple case $P(n_1), P(n_2), \dots, P(n_k)$ to prove $P(n)$; this is still fine as long as the recursion always bottoms out.

The same principle applies to induction on more than one parameter. It's typical, for instance, to prove $P(n,m)$ based on $P(n-1,m)$ and $P(n,m-1)$. However, the more complicated the induction gets, the more necessary it is to prove that your induction steps obey the principle I mentioned above.
For instance, how do you know that Laplace's induction step $P(\binom n2) \implies P(n)$ always bottoms out at an odd value? These numbers get pretty big; for instance, to prove $P(12)$ we use the chain $P(2145) \implies P(66) \implies P(12)$.
A common trick is to find a monovariant $f(n)$ such that whenever we use an induction step $P(n_1) \implies P(n_2)$, we have $f(n_1) < f(n_2)$. (We assume that $f(n)$ is always some nonnegative integer, say, or some other quantity that can't keep decreasing forever). This limits the length of a chain of implications.
In the case of Laplace's induction, the monovariant is pretty tricky to spot. It is the power of $2$ in the prime factorization of $n$. Whenever $n$ is even, $\binom n2$ always has one factor of $2$ less than $n$, so eventually we arrive at an odd base case.
In the case of induction on two parameters, a very common monovariant is the sum of the two parameters: to prove $P(m,n)$, we limit ourselves to only using $P(m',n')$ where $m'+n' < m+n$. This is what we call "induction on $m+n$".
