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.

  • $\begingroup$ Why must each be matched by M? $\endgroup$ – Lindsey May 4 '15 at 18:54
  • $\begingroup$ 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$. $\endgroup$ – Leen Droogendijk May 5 '15 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.