Incidence matrix

Remarks

Example: for the triangle with edges $e_1 = v_1 v_2$, $e_2 = v_2 v_3$, $e_3 = v_1 v_3$, $$B = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix},$$ and each column has exactly two entries $1$, at the ends of its edge. Non-example: a $0$–$1$ matrix with a column containing three entries $1$ is not the incidence matrix of a graph, since an edge has exactly two ends; such matrices describe hypergraphs. Let $D$ be the diagonal matrix of degrees and $A$ the adjacency matrix of a simple graph. Then $B B^{T} = D + A$, and $N N^{T} = D - A$ is the Laplacian matrix for every orientation. Some authors use the transpose, with rows indexed by edges, or the opposite sign convention for $N$. Mathlib defines the unoriented incidence matrix as SimpleGraph.incMatrix.