Let G be a bipartite graph with vertex classes v1 and v2. Let d be a positive integer. Assume that every vertex in v1 has degree at least d and every vertex in v2 has degree at most d. Prove that there exists a matching from v1 to v2 in G.

Thanks!

Printable View

- November 14th 2010, 06:00 PMsaulmundHelp with proof on bipartite graphs!
Let G be a bipartite graph with vertex classes v1 and v2. Let d be a positive integer. Assume that every vertex in v1 has degree at least d and every vertex in v2 has degree at most d. Prove that there exists a matching from v1 to v2 in G.

Thanks!