Hansel's lemma (not Hensel's lemma) states that if the complete graph on $n$ vertices can be expressed as the union of $r$ bipartite graphs $B_1,B_2,\ldots,B_r$ such that $n_i$ is the number of non-isolated vertices in $B_i$, then $n_1+n_2+\cdots+n_r \geq n\log n$. The first published proof of the lemma is by Georges Hansel in 1964, but the lemma has seen several proofs in literature, many of them combinatorial and also an information theoretic proof.
In this talk, we will prove Hansel's lemma using the probabilistic method, and follow it up with an application of the lemma to distance-preserving subgraphs. Specifically, we will show a separation between branching vertices and branching edges by exhibiting an interval graph on $n$ terminal vertices for which every distance-preserving subgraph has $O(n)$ branching vertices and $\Omega(n\log n)$ branching edges [joint work with Prof. Jaikumar].
