We say that a bipartite graph G = (V, E), where V = L R, is d-regular if every vertex V has

We say that a bipartite graph G = (V, E), where V = L ⋃ R, is d-regular if every vertex ν ∈ V has degree exactly d. Every d-regular bipartite graph has |L| = |R|. Prove that every d-regular bipartite graph has a matching of cardinality |L| by arguing that a minimum cut of the corresponding flow network has capacity |L|.