7
$\begingroup$

(This question has been posted on mathoverflow: Generalizing Hall's marriage theorem)

Fix positive integers $m,n,k$ such that $n\geq k$.

Consider a bipartite graph between two sets of vertices $A$ and $B$ consisting of $n$ and $mn$ vertices respectively. Suppose each vertex in $A$ is connected to exactly $mk$ vertices in $B$ and each vertex in $B$ is connected to exactly $k$ vertices in $A$. (Assume there are no double edges between any pair of vertices.)

Is it possible to select a subset $B'$ of $B$ of size $n$ such that each vertex of $A$ is connected to exactly $k$ vertices in $B'$?

This is trivially true when $k=1$, whereas the case $k=2$ is equivalent to Hall's marriage theorem. (This follows from Peterson's 2-factor theorem.) Can we say something for general $k$?

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .