Question

Question 2: A bipartite graph with 2n vertices (namely |V1| = |V2| = n) is d-regular if and only if the degree of every vertex in V1 ∪ V2 is exactly d. Show that a d-regular bipartite graph always has a perfect matching (a matching of size n that includes all vertices).

***Remarks: All the graphs here are without self loops and parallel or anti-parallel edges. A network is a directed graph with source s and sink t and capacity ce > 0 on every edge e. In all the algorithms, always explain their correctness and analyze their complexity. The complexity should be as small as possible. A correct algorithm with large complexity, may not get full credit. The number of vertices is denoted by n, and the number of edges by m. ***

Answer 1

Let G be a bipartite graph with 2n vertices, |v1|=|v2|=n is d- regular. That means degree of each vertex of G either it's from v1 or from v2 is d.

Thus degree of each vertex from v1 U v2 is d exactly  

Conversely , let degree of each vertex from v1 U v2 is d exactly. This implies that degree of each vertex of v1 is exactly d and degree of each vertex of v2 is also d . This implies that every vetex of G has degree d that is G is d regular .

For the second part the proof is as follow:

We want to use Hall’s theorem to guarantee a complete matching, and then show that the complete matching is actually a perfect matching. Let us first show the conditions for Hall’s theorem.

Since the graph is regular and edges go from X to Y. Without loss of generality, consider A⊆X to be an arbitrary subset, and denote by N(A) the set of neighbors of elements of A.

Every edge with an endpoint in A has an endpoint in N(A), let EA and EN(A) denote the respective edge sets.

Then since G is regular (d is the degree of each vertex), |EA|=d|A| and |EN(A)|=d|N(A)|, hence |A|≤|N(A)|.By Hall’s theorem there is a complete matching.

But |X|=|Y|, so every vertex in Y is also matched to a vertex in X, which together match every vertex in the graph. Thus the complete matching is a perfect matching.