I have a bipartite graph $G$ with $n$ vertices in each partition. It is given to us that each vertex on one side has a degree at least $\frac{n}{2}$. I'm supposed to prove that $G$ has a perfect matching.
I'm having a hard time proving this because it seems false. Say $G$ is a bipartite graph with 4 vertices on each side of the partition. Let $A$ = the partition of $G$ s.t. degree of every node in $A \geq \frac{n}{2}$. We can make every vertex in $A$ be incident exactly to 2 vertices in $B$, where $B$ = the rest of the vertices not in $A$.
Doesn't this fit our criterion: both sets of vertices = $n$ and for every vertex $\in A$ it has a degree $\geq \frac{n}{2}$? But there isn't a perfect matching in this graph.
E.g.
A partition B partition
1 5
2 6
3 7
4 8
For each vertex in $A$, there is an edge between $v_i \in A$ and vertices $5$ and $6$ $\in B$.