# Matching in a bipartite graph

Suppose that $G$ is a bipartite graph with bipartition $(A,B)$ and $G$ is $C_4$-free. Prove that if every vertex in $A$ has degree at least $\frac32 x$ and $|A|\leq x^2$, then $G$ has a matching which uses every vertex in $A$.

Would I have to use Hall's Theorem in some way because there is matching or Tuttes?

Assume the statement is not true and let $M$ be a maximum matching, $v$ an unmatched vertex of $A$. Note that the requirement that $G$ is $C_4$-free means, that two vertices cannot have 2 common neighbours. Let $t=\lceil{\frac32x}\rceil$.

$v$ has at least $t$ neighbours in $B$ that are all matched by $M$, call them $b_1,\ldots,b_t$ and let $a_1,\ldots,a_t$ be the vertices of $A$ such that $a_ib_i$ is an edge of $M$. Each of the $a_i$ has at least $t-1$ neighbours in $B$ that must be different from all $b_i$ and each of them must be matched by $M$ (why?).

So $a_1$ has at least $t-1$ neighbours different from the $b_i$, call this set $A_1$.

$a_2$ has at least $t-1$ neighbours different from the $b_i$, and it can only have one neighbour in common with $a_1$, so there is a set $A_2$ of size at least $t-2$ this is disjoint from both the $b_i$ and $A_1$.

Continuing this way (make a nice induction argument if you like), we find $t+(t-1)+\ldots+1$ different elements of $B$, all matched by $M$, so $A$ also must have at least this number of elements.

Since $t+(t-1)+\ldots+1=\frac{t(t+1)}2\geq\frac{\frac94x^2}2>x^2$ we found a contradiction.

• Why must each be matched by M? – Lindsey May 4 '15 at 18:54
• If $a_i$ would have a neighbor $c$ that is not matched by $M$, then $vb_ia_ic$ is an $M$-augmenting path, contradicting the maximality of $M$. – Leen Droogendijk May 5 '15 at 6:14