Incidence matrix

The incidence matrix of a Graph G is a matrix $[b_{ij}]$ of dimensions $pXq$ where p and q are the number of vertices and edges respectively, such that $b_{ij}=1$ if the vertex $v_{i}$ and edge $x_{j}$ are incident and 0 otherwise.

The incidence matrix is related to the adjacency matrix of a graph by the following theorem:

$A(G)=B(G)^{T}B(G)-2I_{q}$

where $A(G)$ and $B(G)$ are the adjacency matrix and incidence matrix respectively and $I_{q}$ is the identity matrix of dimension q.