Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
