I need to show that if G is simple and $(X,Y)-$bipartite has perfect match if $|X|=|Y|=k, |E(G)| > k*(k-1)$.
I understand this is a simple problem, but I could not find a proof or hints.
I showed that $\delta G\ge1$ (minimum degree of any vertex). I think a good strategy, that I "guess" (but only guess) is correct, is to show the graph has a 1-factor. I could not think of a way to go about this.
By contradiction I tried using Hall:
$\exists S \subset X$ such that $|S| < |Adj(S)|$. However, I had problems writing that it is impossible.
I also tried using induction in $|X|$:
I believe I should be able to select and edge add it to a match and say that the rest of the match comes from the induction hypothesis. I select $v$ with the smallest degree, then I select the edge that leads to the neighbor $u$ with lowest degree. However, I could not write the graph $G' = G - u - v$ has $|E(G')| > (k - 1)*(k-2)$
Is any of what I tried leading to a correct path? How could I show it has a 1- factor, if it has?
This is true if every vertex has positive degree. Indeed, consider the bipartite graph where every one of the $k$ vertices in $X$ has degree $k-1$ and $k-1$ vertices in $Y$ have degree $k$ but the $k$th vertex has degree 0. Then there is no perfect matching despite $G$ having the required number of edges.
ETA: If $G$ has more than $k(k-1)$ edges then this condition of every vertex having positive degree will be achieved. [I misread and saw $G$ having only st least $k(k-1)$ edges.
If every vertex has positive degree in $G$ then $N_G(X) = Y$ and $N_G(Y) = X$ and $|X|=|Y|$. So we now show that $|N_G(S)| \geq |S|$ for each nonempty $S$ of cardinality strictly less than $k$.
Let $S$ be a subset of $X$ and let us assume that $|S| \ge 2$. Let us write $b = |N_G(S)|$ and $a = |S|$. Then
Then $|A(G)| \le bk + (k-b)(k-a)$. [Indeed, the $b$ vertices in $N_G(S)$ can have degree at most $k$, and the $k-a$ vertices in $Y \setminus N_G(S)$ are each not adjacent to any of the $a$ vertices in $S$ so these vertices can have degree at most $k-a$.]
However, $kb+(k-b)(k-a)$ $=$ $k^2-ak+ab$. If $b$ satisfies $b<a$ then $ab < (a-1)k$ [indeed, put $b \le a-1$ and $a < k$], giving $|A(G)|$ $\le$ $k^2-ak+ab$ $<$ $k^2-ak+(a-1)k$ $=$ $k(k-1)$, a contradiction.