Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A problem in graph theory

  1. Jun 16, 2011 #1
    1. The problem statement, all variables and given/known data

    Let G=A U B be a bipartite graph. For each a in A and for each b in B we have d(a)≥d(b)≥1 where d(v) is the degree of vertex v. Show that there exists a matching which saturates A.

    2. Relevant equations

    3. The attempt at a solution

    I guess I need to use Hall's Theorem, but I don't see how.
  2. jcsd
  3. Jun 17, 2011 #2
    Solved it, thanks :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook