Let G be a graph with 2n vertices, and assume either deg v ≥ n for each vertex v, or |E| ≥ 1 2 (2n − 1)(2n − 2) + 2. Show that G has a perfect matching. Hint: Derive these assertions from a more general result involving Hamiltonian cycles. Example 13.2.1 illustrates the following simple but fundamental result due to Berge [Ber57].
