1
$\begingroup$

Suppose you have the $K_{2n}$ covered by a multigraph consisting of $2n-1$ bicliques, each consisting of a partition of the vertex set into two sets of equal size.

Here is a picture of $K_{6}$ with 5 bicliques.

enter image description here

My question is: under which circumstances is it possible to pick a perfect matching of each biclique, such that every edge of $K_{2n}$ is covered exactly once?

I know so far, that obviously every edge should be covered at least once and every vertex has $n$ edges of one color. Moreover a biclique can only occur at most $n-1$ ($n$ odd) or $n$ ($n$ even) times.

Is there any theory regarding this question?

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .