Covering multigraphs with bipartite graphs

Hansel’s lemma states that ${\sum }_{H\in \mathcal{H}}\mathrm{\mid }H\mathrm{\mid }\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}}\mathrm{\mid }H\mathrm{\mid }$ which shows that our generalization is asymptotically tight in some sense.