I am aware that Hall's Marriage theorem for complete matching goes like "A bipartite graph $G$ with bipartition $(V_1, V_2)$ has a complete matching from $V_1$ to $V_2$ if and only if $$ |N(A)| \geq |A|, \forall A \subseteq V_1$$

I want to know in which cases does an equality hold, i.e. $$ |N(A)| = |A|, \forall A \subseteq V_1 $$

Any help is greatly appreciated.


This can only hold if every vertex of $V_1$ has degree $1$ exactly (so the graph is a disjoint union of edges).

Why? Consider each vertex $u\in V_1$ as the singleton set $A=\{u\}$. If it has any number of neighbors not equal to one, you've already found a set breaking the equality.


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.