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!
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!