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.

  • $\begingroup$ Start by defining your terms. All those symbols you use --- what do they stand for? $\endgroup$ – Gerry Myerson Jun 24 '14 at 7:03
  • $\begingroup$ Good. What's the source of the question, please? $\endgroup$ – Gerry Myerson Jun 24 '14 at 10:03
  • $\begingroup$ It's from math contest training, but I don't know where my teacher have taken from. $\endgroup$ – pointer Jun 24 '14 at 10:35
  • $\begingroup$ Do you know if the graph is simple, or can it also be a multigraph? $\endgroup$ – Studentmath Jun 30 '14 at 23:08
  • 1
    $\begingroup$ Certainly. $~~~~~~$ $\endgroup$ – pointer Jul 3 '14 at 18:26

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)$.

  • 1
    $\begingroup$ Wow this is amazing! $\endgroup$ – Gina Jul 4 '14 at 15:31

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.$

  • $\begingroup$ You say "it is easy to see that k′=k". Could you please show your derivation of this claim if it is different from that of EuYu? $\endgroup$ – Hans Jul 19 '14 at 4:04
  • $\begingroup$ Try to compute number of one's in matrix $A$ with two ways. $\endgroup$ – pointer Jul 19 '14 at 14:02
  • $\begingroup$ Right, consider the quadratic form $e^T Ae$. Thanks. There is perhaps one typo, should it not be $e^T = (1,1,\ldots,1)$? $\endgroup$ – Hans Jul 19 '14 at 14:14
  • $\begingroup$ Yes you are right, but it doesn't change things much. $\endgroup$ – pointer Jul 19 '14 at 14:57

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.