Problem on bipartite graphs.

Let's $G$ is bipartite graph with sides $X=\{v_1,v_2,\ldots,v_n\}$ and $Y=\{u_1,u_2,\ldots,u_n\}.$ Let $|N_G(v_i)|=k$ and $|N_G(v_i)\cap N_G(v_j)|=d\lt k~,(i\ne j)$. Prove that $|N_G(u_i)|=k$ and $|N_G(u_i)\cap N_G(u_j)|=d,~(i\ne j)$. $N_G(v)$ is neighborhood of vertex $v$ in graph $G$.

I have no idea how I can start the proof.

Solution 1:

Let $A$ denote the adjacency matrix for the graph. We order the vertices in such a way that we may write $$A = \begin{pmatrix} 0 & B\\B^\mathrm{T} & 0\end{pmatrix}$$ Note that a decomposition like this is possible for any bipartite graph. The matrix $B$ represents the incidences of $X$ in $Y$. Note that by assumption of $|X|=|Y|=n$, the matrix $B$ is an $n\times n$ square matrix. Also note that $B$ is a $0$-$1$ matrix.

The conditions that $|N_G(v_i)|=k$ and $|N_G(v_i)\cap N_G(v_j)| = d<k$ now translate to $$\mathbf{b}_i\cdot \mathbf{b}_j = (k-d)\delta_{ij}+d$$ where $\mathbf{b}_i$ denotes the $i$th row of the matrix $B$. The above condition of course implies that $$BB^\mathrm{T} = (k-d)I_n + dJ_n\tag{*}$$ where $I_n$ is the identity matrix and $J_n$ is the matrix of all ones.

Lemma: A $0$-$1$ square matrix $B$ which satisfies ($*$) with $k>d$ is an invertible normal matrix.

Proof: The eigenvalues (up to multiplicity) of $J_n$ are $n$ and $0$, therefore the eigenvalues of $BB^\mathrm{T}$ are $k+(n-1)d$ and $k-d$. In particular, this means that $BB^\mathrm{T}$ is invertible and hence $B$ is also invertible.

Notice now that $B$ satisfies $$BJ = kJ,\ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ J=kB^{-1}J$$ Right-multiplying $(*)$ by $J$ gives $$BB^\mathrm{T}J = (k-d)J + dJ^2 = (k-d)J + ndJ = [k+(n-1)d]J$$ Applying $B^{-1}$ to the above, we get $$B^\mathrm{T}J = [k+(n-1)d]B^{-1}J = \frac{k+(n-1)d}{k}J$$ Taking the transpose of the above, we get $$JB = \frac{k+(n-1)d}{k}J$$ Right-multiplying by $J$ yields $$JBJ = n\frac{k+(n-1)d}{k}J$$ On the other hand, we also know that $BJ = kJ$ so that $$JBJ = nkJ$$ On comparison, we must have $$k = \frac{k+(n-1)d}{k}$$ Therefore we get $$JB = kJ = BJ$$ and consequently $B$ and $B^\mathrm{T}$ commutes with $BB^\mathrm{T}$. Therefore $$B^\mathrm{T}B = B^\mathrm{T}(BB^\mathrm{T})(B^T)^{-1} = (BB^\mathrm{T})[B^\mathrm{T}(B^\mathrm{T})^{-1}] = BB^\mathrm{T}$$ as required. $\square$

Finally, note that $$B^\mathrm{T}B = (k-d)I_n + dJ_n$$ is precisely the condition required for $|N_G(u_i)| = k$ and $|N_G(u_i)\cap N_G(u_j)|=d$, which completes our proof. In addition, we have the following corollary as revealed by the proof.

Corollary: If $G$ satisfies the mentioned hypotheses, then $k^2 - k = (n-1)d$. $\square$

Note that the above corollary has a simple combinatorial interpretation. Fix an arbitrary vertex $v\in X$ and consider the number of ways we can reach some other vertex $v\neq v'\in X$ in $2$ steps. We count this in $2$ ways.

First, since $v$ has $k$ neighbors in $Y$, we may choose any of the $k$ neighbors. Each neighbor of $v$ also has $k$ neighbors, one of which is $v$ itself. Therefore we may reach some vertex $v'\in X$ in $k(k-1)$ ways.

Alternatively, each of the $n-1$ other vertices of $X$ shares a size $d$ neighborhood with $v$. Therefore each $v'\in X$ may be reached in precisely $d$ ways from $v$. The total number of ways from $v$ to some other $v'$ is therefore $d(n-1)$.

Solution 2:

As I promised here is the solution.

Let's $A=(a_{ij})_{i,j=1}^n$ be the following matrix: $a_{ij}=1,$ if $\{v_i,u_j\}$ is edge of graph $G$ and $a_{ij}=0,$ otherwise. From the conditions it follows that $AA^T=dB+(k-d)I,$ where $B$ is a matrix with all entries equal $1$. It is easy to check (by finding determinant or by proving that columns independent) that $det(AA^T)\ne0,$ therefore $det(A)\ne0$. So we have $$A^TA=A^{-1}(AA^T)A=dA^{-1}BA+(k-d)I.$$ Now to complete the proof we need to prove that $A^{-1}BA=B,$ that is, $AB=BA$. Let $e^T=(1,1,\ldots,1)$, then $e$ is an eignvector for $A$ (therefore for $A^{-1}$ too) and also for $AA^T$. So $e$ is an eignvector for $A^{-1}(AA^T)=A^T$, $A^Te=k'e.$ As $k'n=e^TAe=kn$, $k'=k$. Therefore $eA=ke~\Rightarrow~BA=kB=AB.$