Counting Neighbours in a Bipartite Graph

Question

In the given graph, it is known that more than $$ \frac{2}{5}n = \left \lfloor \frac{2}{5}\times (5k+2)\right \rfloor = 2k $$ vertices in set $Y$ are connected to any $2$ vertices in set $X$.

How can we show that there are $2$ vertices in $X$ with

$$ \left\lfloor \frac{2}{5}n \right\rfloor +2 = 2k+2 $$ common neighbours in $Y$ and any $2$ of the remaining $4$ vertices in $X$ have exactly $$ \left \lfloor \frac{2}{5}n\right\rfloor + 1 = 2k+1 $$

common neighbours in $Y$?

Answer 1

This is a lovely question which appears complicated but has a very simple answer.

Form a new bipartite graph.

Set Y stays the same but each vertex of X' represents a pair of points of X. We draw an edge between $\{x_1,x_2\}$ of X' and $y$ of Y if $y$ is a neighbour of both $x_1$ and $x_2$.

Set Y has $5k+2$ vertices. One has degree $\begin{pmatrix}5\\2\\\end{pmatrix}=10$ and all the others have degree $\begin{pmatrix}4\\2\\\end{pmatrix}=6$. The number of edges in our new graph is therefore $$10+6(5k+1)=30k+16.$$

Set X' has $\begin{pmatrix}6\\2\\\end{pmatrix}=15$ vertices and each one has degree at least $2k+1$. (Since every pair of vertices of X has at least $2k+1$ neighbours in common.)

To add up to $30k+16$ edges only one of the vertices of X' can have degree more than $2k+1$ and that vertex must have degree precisely $2k+2.$

The result is proved.

N.B. The number of edges on your diagram should be $4n+1$.