Bipartite graph with big degrees
Task number: 4000
Let \( G \) be a bipartite graph with \( 2n \) vertices such that each of its classes of bipartition has \( n \) vertices.
Assume that the minimum degree in \( G \) is at least \( n / 2 \). Prove that \( G \) contains a perfect matching.
Must \( G \) contain a perfect matching if the minimum degree is \(\lceil n / 2 \rceil-1 \)?