When performing induction on say a graph $G=(V,E)$, one has many choices for the induction parameter (e.g. $|V|, |E|$, or $|V|+|E|$). Often, it does not matter what choice one makes because the proof is basically the same. However, I just read the following ingenious proof of König's theorem due to Rizzi.


**König's theorem.** For every bipartite graph $G$, the size of a maximum matching $v(G)$ is equal to the size of a minimum vertex cover $\rho(G)$.


**Proof.** Induction on $|V|+|E|$. Base case is clear. Now if $G$ has maximum degree 2, then $v(G)=\rho(G)$, so we may assume that $G$ has a vertex $x$ of degree at least 3. Let $y$ be a neighbour of $x$ and let $Y$ be a minimum vertex cover of $G - y$. Evidently, $Y \cup y$ is a vertex cover of $G$. But, by induction $|Y|=v(G-y)$, so we are done unless $v(G)=v(G-y)$. Thus, $G$ has a maximum matching $M$ avoiding $y$. Let $e \in E - M$ be incident to $x$ but not to $y$. By induction, 


$v(G)=|M|=v(G-e)=\rho(G-e)$. 


Let $Z$ be a vertex cover of $G-e$ of size $|M|$. Note that $y \notin Z$, since $M$ does not cover $y$. This implies $x \in Z$, since $xy \in E$. But then $Z$ also covers $e$ and hence is a vertex cover of $G$. 



> 
> **Question.** What are some other instances (not necessarily in graph theory), where simply changing the induction parameter results in a nice shorter proof?
> 
> 
> 



Easier induction proofs by changing the parameter
Cauchy's proof by induction of the inequality between the arithmetic and geometric means (written in his 1821 *Cours d'Analyse*).


Of course, the base of the induction, for $n=2$, immediately comes from $(\sqrt x\_1-\sqrt x\_2)^2\ge0$, but then, although it is actually possible to follow the natural induction steps, making the inequality $M\_G\le M\_A$ for $n+1$ nonnegative real numbers follow from the inequality for $n$ numbers, it appears that the other implication is much easier: actually, the inequality for $n$ numbers can be easily seen as a particular case of the inequality for $n+1$ numbers. (For $n$ numbers, just append to them their arithmetic mean as an $(n+1)$-th number, use the inequality for $n+1$ numbers, and simplify). Also, the inequality for $2n$ numbers easily follows from the inequalities resp. for $2$ and for $n$ numbers. As a consequence, we have an induction proof that follows a funny jumping path along natural numbers (if you like to see it this way; that's not exactly Cauchy's description): $(2)\Rightarrow (4)\Rightarrow (3)\Rightarrow (6)\Rightarrow (5)\Rightarrow (10)\Rightarrow (9)\Rightarrow(8) \Rightarrow(7) \Rightarrow (14)\Rightarrow \dots$


