Consider a bipartite graph $G=(L\cup R,E)$ where $|L|=|R|=k$. The set of neighbors of a vertex $v\in V$ is defined as $N(v)$. The bipartite graph has the following properties:

1) $|N(v)|\geq 1$

2) $|\bigcup_{\forall l \in L}N(l)|=k$

Prove that a perfect matching exists for the bipartite graph $G$.

I know that I have to use Hall's marriage theorem here but I don't know how to prove that for all subsets of $L$, the number of neighbors is as big as the subsets for $G$.


It is false for all $k\geq 3$. Consider the bipartite graph which has a special vertex $r\in R$ and $l\in L$ such that an edge is part of the graph if and only if $r$ or $l$ is one of the endpoints.

A counterexample for $k=3$:

enter image description here

  • $\begingroup$ Could you please elaborate your answer with an example. $\endgroup$ Oct 18 '16 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.