Ossowski theorem about bipartite graph without cliques

Question

I was reading the proof of Ossowski theorem about bipartite graphs without $(r+1-a)\times a$ cliques for $a=1,\dots,r$.

I think that I got the general idea behind the proof but there is one techinical detail which is bothering me. I would be very thankful if you can explain it in a simple way to understand.

Thanks a lot for attention!

Answer 1

The set $X\subset V_1$ has been chosen as a minimal subset of vertices so that after removal of $X$ the resulting graph does not contain cliques of size $(r+1-a)\times a$ for $1\leq a\leq r$.

What does it tell us? If we take any $x\in X$ the subset $X\setminus \{x\}$ is not mininal anymore! It immediately implies that there is a clique of size $(r+1-a)\times a$ for some $a\in\{1,\dots,r\}$. It is equivalent to the existence $Y_x\subset V_2$ with $1\leq |Y_x|\leq r$ and $$|N(Y_x)\setminus (X\setminus\{x\})|+|Y_x|=r+1.$$ Notice that for each $x\in X$ we have some $Y\subset V_2$, i.e. the set $Y$depends on $x$ and that is why I denote it as $Y_x$.

I claim that $x\in N(Y_x)$. Otherwise, if $x\notin N(Y_x)$, then $|N(Y_x)\setminus (X\setminus\{x\})|=|N(Y_x)\setminus X|$ and you will get a contradiction because $|N(Y_x)\setminus X|\leq r-|Y_x|$.

Hence $x\in N(Y_x)$, then $|N(Y_x)\setminus (X\setminus\{x\})|=|N(Y_x)\setminus X|+1$. Therefore $|N(Y_x)\setminus X|+|Y_x|=r$.

I was able to show that for each $x\in X$ there is $Y_x\subset V_2, \ 1\leq |Y_x|\leq r, \ x\in N(Y_x)$ and $|N(Y_x)\setminus X|+|Y_x|=r$.

Hope it helps!