[Math] Relation between Adjacency Matrix and Incidence Matrix

graph theorylinear algebra

Let the Adjacency matrix be A, and Incidence Matrix be B;
'd' represents degree of given vertex

How do we prove $B.B^T=A+\begin{bmatrix}d(V_1) & 0 &\dots \\ 0 & d(V_2) & 0 & \dots\\ 0 &0 & d(V_3)&0&\dots \\ \vdots & & & \ddots \\ 0 &\dots & & & d(V_n) \end{bmatrix}$

Best Answer

  1. What does each column $b_j$ of B encode, geometrically?
  2. Can you show that $b_i\cdot b_j$ computes the number of edges that vertex $i$ and $j$ share?
  3. The theorem should now be straightforward: consider the three cases where two vertices $i,j$ are adjacent, not adjacent, and equal.