Skip to main content
Post Closed as "Not suitable for this site" by bof, Emil Jeřábek, Alex M., ARG, Hugh Thomas
added capitals and tag
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

expanding hall's Expanding Hall's theorem

Source Link
Blur
  • 19
  • 1

expanding hall's theorem

I'm trying to get a "feel" about Hall's theorem and try to expand it for one to many matching. So my question is:

Given a bipartite graph, what would be a neccessary and sufficient condition for that it would be possible to match every vertex on one side, to two vertices on the other side, that would belong only to him.

Iv'e "cloned" the vertices on the "one side", and for each edge from v to u where v is on the "one side" and u is on the other side, Iv'e connected an additional edge between v_clone and u. I'm trying to figure out what would be the condition(s)? when I return to my original graph. And how can I prove it? Thanks!