2
$\begingroup$

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:

  1. Why is this type of induction the right technique?
  2. 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?
$\endgroup$
5
  • $\begingroup$ Can I know a source for where you are reading Graph theory (in particular, this proof of Mader's theorem) from? I found this question as an exercise in Diestel's book on Graph Theory. $\endgroup$ Commented Jun 26, 2021 at 13:09
  • $\begingroup$ It’s a set of lecture notes, no book. But I looked around and definitely it’s something that is used in graph theory, I don’t think it’s an idiosyncratic preference of the author of my notes. $\endgroup$
    – Karl
    Commented Jun 26, 2021 at 14:30
  • $\begingroup$ The "induction parameter" can be just about anything, as long as $(1)$ it is well ordered, and $(2)$ every relevant case is "parameterized" by it. The best reason for an exotic choice of induction parameter is often that it captures the right structure. In your proof, have you considered what would occur if you inducted on $t$ alone? $\endgroup$
    – While I Am
    Commented Jun 26, 2021 at 14:30
  • $\begingroup$ The problem with inducting on t alone would be that I would run into problems with the graph having too few vertices? $\endgroup$
    – Karl
    Commented Jun 26, 2021 at 14:31
  • 1
    $\begingroup$ I think I found the proof that you are referring to in the ETH repository. I'm just going through it to try and understand why it was done there. From what I see, I kind of understand what I need to answer your question, but I'm going to need time. $\endgroup$ Commented Jun 26, 2021 at 15:26

1 Answer 1

4
$\begingroup$

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$".

$\endgroup$
4
  • $\begingroup$ Thanks a lot for your answer. What do you think drives the necessity of such an induction in that Mader proof, or in graph theory in general? The fact that one needs to “exhaust” all the parameters involved in the theorem? At first sight, one could think that on Mader theorem one just needs induction on the number of vertices and to prove it for a fixed t. $\endgroup$
    – Karl
    Commented Jun 26, 2021 at 16:20
  • 2
    $\begingroup$ Often you need something like this when the induction uses multiple previous cases: some where only the number of vertices decreases; some where only $t$ decreases. But it's also true that this is common enough in graph theory that sometimes people use this style of induction even when they don't need it. $\endgroup$ Commented Jun 26, 2021 at 16:29
  • 1
    $\begingroup$ @Karl I thought about this : Mader's theorem concerns minors, which form by edge contraction and/or subgraph consideration. Once you see this, it suggests induction immediately , but you have to use a variable which considers both subgraph contraction (i.e. $G(V)$) and edge contraction (which, once you realize that choosing the right edge can optimally increase/retain the degree, suggests that some function of average degree be taken into account). It is also possible to prove the theorem using extremal considerations : a proof which transforms to induction somewhat naturally. $\endgroup$ Commented Jun 26, 2021 at 16:40
  • $\begingroup$ @Karl I think a lot of proofs of induction on graphs have to do with the fact that existence of a certain property is retained(possibly reduced) across specific (to be more precise : extremal) removal/contraction of edges or vertices, whether it be minor existence, or the existence of a cycle, or some kind of path etc. . That is always what helps the "inductive" part of the argument, with the base case usually being a formality. That's why induction and the extremal principles work so well! $\endgroup$ Commented Jun 26, 2021 at 16:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .