edited tags; [made Community Wiki]
Easier induction proofs by changing the parameter
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,
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$.