Covering multigraphs with bipartite graphs

Abstract

Hansel's lemma states that ${\sum }_{H\in \mathcal{H}}|H|\ge n{\log }_{2}n$ holds where $\mathcal{H}$ is a collection of bipartite graphs covering all the edges of $K_n$. We generalize this lemma to the corresponding multigraph covering problem and the graphon covering problem. We also prove an upper bound on ${\sum }_{H\in \mathcal{H}}|H|$ which shows that our generalization is asymptotically tight in some sense.

13 pages