Hi we need help with this problem, we turned a solution in, but didn't get a good explanation of what we did wrong. Can someone tell us what we should be doing or write out a solid proof? We need it to study for the exam.
For $k,n\in\mathbb{N},$ let $G$ be an $A,B$-bigraph with $|A|=n=|B|$ such that $\delta(G)\geq k$, and for all $X\subseteq A,Y\subseteq B$, if $|X|,|Y|\geq k$ then $|E(X,Y)|\ne\emptyset$. Prove: $G$ has a perfect matching.
This is what my groupmate wrote
First note that if there is a matching such that $A$ is $M-saturated$ then we are done because $\mid A \mid = \mid B \mid =n$ and we cannot have common ends in our matching. I wish to show that this graph satisfies the conditions of Hall's theorem. Suppose that $S \subseteq A$; if $\mid S \mid \leq k$ the conditions that $\delta(G) \geq k$ ensures that $\mid N(S) \mid \geq \mid S \mid $, so suppose otherwise.
We still have that $N(S) \geq k$, suppose that $v \in B - N(S)=N(S)^c $(relative to $B$). We have that $d(v) \geq k$ and since $v \not \in N(S)$ this implies that $\mid S \mid \leq n-k$. If we did have $N(S)^c \geq k$ that would imply an connection between $S$ and $N(S)^c$, a contradiction. Therefore $\mid N(S) \mid > n-k$ and we have $\mid N(S) \mid > \mid S \mid $. From Hall's theorem we have $A$ as saturated by some matching, and by the remarks earlier $B$ is saturated as well. Therefore there exists a perfect matching for this graph.
This looks correct. You could probably clean up the proof by explaining a bit more, but the idea seems good.
When you say $M$-saturated, you could say for any matching $M$. So it suffices to find a matching that saturates $A$. You then prove such a matching exists using Hall's theorem.
In the final paragraph, you could explain the statement "If we did have $N(S)^c \geq k$, this would imply a connection between $S$ and $N(S)^c$" by saying: $|S| \geq k$ by assumption and if $X \subseteq A$, $Y \subseteq B$ with $|X|,|Y| \geq k$, we have $E(X,Y) \not= \emptyset$. Hence $|N(S)^c| < k$, i.e. $|N(S)| > n-k$ because $|N(S)| + |N(S)^c| = |B| = n$.
It's always a good idea to explicitly state when you're using all the given hypotheses--partially as a sanity check. Most of this is just being nit-picky to make it clearer to whoever is grading, the overall idea looks solid!