Let \(D\) be a digraph with finite vertex set \(V\) and finite arc set \(A\), each arc \(a\) having a tail and a head in \(V\), and let \(F\) be a field. Let \(M\) be the oriented incidence matrix of \(D\) over \(F\), the \(V \times A\) matrix whose row \(m_v\) records, for each arc, whether \(v\) is its tail (\(+1\)), its head (\(-1\)), or neither (\(0\)). Then the bond space \(\mathcal{B} \subseteq F^{A}\) of \(D\) — the space of potential differences — coincides with the row space of \(M\), that is, with the subspace of \(F^{A}\) spanned by the rows \(\{ m_v : v \in V\} \).

Let \(D\) be a directed graph with finite vertex set \(V\) and finite arc set \(A\), and let \(F\) be a field. Equip the space \(F^A\) of \(F\)-valued functions on the arcs with the standard dot-product bilinear form \(\langle f, g\rangle = \sum _{a \in A} f(a)\, g(a)\). Then the cycle space \(\mathcal{C} \subseteq F^A\) (the circulations) is exactly the orthogonal complement of the bond space \(\mathcal{B} \subseteq F^A\) (the potential differences) with respect to this form; that is, \(\mathcal{C} = \{ \, f \in F^A : \langle f, g\rangle = 0 \text{ for all } g \in \mathcal{B} \, \} \).

Let \(D\) be a digraph with finite vertex set \(V\) and finite arc set \(A\), and let \(F\) be a field. If \(f \colon A \to F\) is a circulation on \(D\) — that is, \(f\) lies in the cycle space \(\mathcal{C}\) — and \(f\) is not identically zero, then there exists an arc-cycle \(c\) in \(D\) (a nonempty closed arc-sequence) all of whose arcs lie in the support of \(f\), i.e. every arc appearing in \(c\) satisfies \(f(a) \neq 0\).

Let \(D\) be a directed graph with finite vertex set \(V\) and finite arc set \(A\), and let \(F\) be a field. Suppose \(g \colon A \to F\) is a potential difference in \(D\) — that is, \(g\) lies in the bond space \(\mathcal{B}\) — and that \(g\) is not identically zero. Then there is a bond \(B\) of \(D\) (a minimal nonempty edge cut) all of whose arcs lie in the support of \(g\), i.e. \(B \subseteq \{ a \in A : g(a) \neq 0\} \).

Let \(D\) be a digraph with finite vertex set \(V\) and finite arc set \(A\), each arc \(a\) assigned a tail and a head in \(V\), and let \(F\) be a field. Write \(\mathcal{B} \le (A \to F)\) for the bond space of \(D\), the space of potential differences \(\delta p\) arising from functions \(p\) on \(V\). Suppose \(B\) is a basis matrix of \(\mathcal{B}\), so that the rows of \(B\) form a basis of \(\mathcal{B}\), and let \(S \subseteq A\). Then the columns of the restricted matrix \(B \mid S\), indexed by the arcs in \(S\), are linearly independent over \(F\) if and only if \(S\) is acyclic, i.e. contains no arc-cycle of \(D\).

Let \(V\) and \(A\) be finite sets of vertices and arcs, let each arc \(a\in A\) have a tail \(\mathrm{tail}(a)\in V\) and a head \(\mathrm{head}(a)\in V\), and let \(F\) be a field, so that the cycle space \(\mathcal{C}\le (A\to F)\) is defined. Let \(C\) be a basis matrix of \(\mathcal{C}\) — a matrix whose rows form a basis of \(\mathcal{C}\) — and let \(S\subseteq A\) be a finite set of arcs. Then the columns of the restriction \(C\mid S\) (the submatrix of \(C\) keeping exactly the columns labelled by elements of \(S\)) are linearly independent over \(F\) if and only if \(S\) contains no bond, that is, there is no bond \(B\) with \(B\subseteq S\).

Let \(D\) be a digraph with finite vertex set \(V\) and finite arc set \(A\), specified by its tail and head maps \(A \to V\), and let \(G\) be the underlying simple graph of \(D\). Working over the real field, the bond space \(\mathcal{B}\) of \(D\) — the space of potential differences on the arcs — satisfies

where \(\omega \) is the number of connected components of \(G\).

Let \(D\) be a digraph with finite vertex set \(V\) and finite arc set \(A\), given by its tail and head maps, and let \(G\) be its underlying simple graph. Then, working over \(\mathbb {R}\), the dimension of the cycle space \(\mathcal{C}\) of \(D\) is

where \(\omega \) is the number of connected components of \(G\).

Let \(D\) be a digraph with finite vertex set \(V\) and finite arc set \(A\), and let \(F\) be a field. Fix a maximal forest \(T\) of \(D\). For each arc \(a \notin T\), the subgraph \(T + a\) contains a unique cycle, and we write \(f_a\) for the \(F\)-valued circulation associated with this fundamental cycle. Then the family \((f_a)_{a \notin T}\), viewed as the rows of a matrix whose row index ranges over the arcs outside \(T\), is a basis matrix of the cycle space \(\mathcal{C}\) of \(D\) over \(F\): these circulations are linearly independent and their span is all of \(\mathcal{C}\).

Let \(D\) be a finite digraph with vertex set \(V\) and arc set \(A\), specified by its tail and head maps \(A \to V\), and let \(F\) be a field. Let \(T\) be a maximal forest of \(D\), and for each arc \(a \in T\) let \(g_a\) denote the potential difference of the fundamental bond of \(a\), that is, \(g_a = \delta p_a\) where \(p_a\) is the indicator function of the vertex set of that bond. Then the matrix over \(F\) whose rows are the functions \(g_a\), indexed by the arcs \(a \in T\), is a basis matrix of the bond space \(\mathcal{B}\) of \(D\); equivalently, the family \((g_a)_{a \in T}\) is a basis of \(\mathcal{B}\).

Let a finite digraph be given by its tail and head maps on a finite arc set \(A\), and let \(T\) be a spanning tree of this digraph. If \(B\) is the integer basis matrix of the bond space corresponding to \(T\) — its rows indexed by the arcs of \(T\) — then \(B\) is unimodular; that is, every full square submatrix of \(B\) (a submatrix whose columns are picked out by an injective column selection) has determinant \(0\), \(+1\), or \(-1\).

Let \(D\) be a finite digraph with vertex set \(V\) and arc set \(A\), specified by its tail and head maps \(A \to V\), and let \(T \subseteq A\) be a spanning tree of \(D\). Let \(B\) be the integer basis matrix of the bond space corresponding to \(T\), with rows indexed by the arcs of \(T\) and columns indexed by all of \(A\). Then the number \(\tau (D)\) of spanning trees of \(D\) satisfies

Let \(T\) be a spanning tree of a finite digraph on vertex set \(V\) with arc set \(A\), and let \(C\) be the integer basis matrix of the cycle space corresponding to \(T\) — the matrix whose rows are indexed by the arcs outside \(T\) and whose columns are indexed by all of \(A\). Then \(C\) is unimodular: every full square submatrix of \(C\) formed by selecting a set of columns equal in number to the rows has determinant \(0\), \(+1\), or \(-1\).

Let \(G\) be a directed graph with finite vertex set \(V\) and finite arc set \(A\), each arc assigned a tail and a head in \(V\), and let \(\tau \) denote the number of spanning trees of \(G\). Fix a spanning tree \(T \subseteq A\), and let \(C\) be the integer matrix over the cycle space of \(G\) that is the basis matrix corresponding to \(T\), so that its rows are indexed by the arcs \(a \notin T\) and its columns by the arcs of \(A\). Then

Let \(G\) be a finite digraph with vertex set \(V\) and arc set \(A\), and let \(T\) be a spanning tree of \(G\). Let \(B\) be the basis matrix of the bond space \(\mathcal{B}\) corresponding to \(T\), whose rows are indexed by the arcs of \(T\), and let \(C\) be the basis matrix of the cycle space \(\mathcal{C}\) corresponding to \(T\), whose rows are indexed by the arcs not in \(T\); both have integer entries and columns indexed by all of \(A\). Form the square integer matrix \(M\) with rows indexed by \(A\) by assigning to each arc of \(T\) its row of \(B\) and to each remaining arc its row of \(C\). Then the number \(\tau (G)\) of spanning trees of \(G\) satisfies \(\tau (G) = \det M\) or \(\tau (G) = -\det M\); that is, \(\tau (G) = \left\lvert \det M\right\rvert \).

The matrix-tree theorem (Kirchhoff, 1847). Let \(D\) be a connected digraph with vertex set \(V\) and arc set \(A\), and let \(M\) be its oriented incidence matrix, the \(V \times A\) matrix whose entry in row \(v\) and column \(a\) is \(1\) if \(v\) is the tail of \(a\), is \(-1\) if \(v\) is the head of \(a\), and is \(0\) otherwise. Fix any vertex \(y \in V\), and let \(K\) be the reduced incidence matrix obtained from \(M\) by deleting the row indexed by \(y\). Then the number \(\tau (D)\) of spanning trees of \(D\) satisfies

the equality holding in \(\mathbb {Z}\).

Let \(D\) be a finite digraph with vertex set \(V\) and arc set \(A\), where each arc \(a\) has a tail and a head in \(V\), and let \(M\) be its oriented incidence matrix over \(\mathbb {Z}\): the rows are indexed by \(V\), the columns by \(A\), and the \((v,a)\) entry equals \(1\) if \(v\) is the tail of \(a\), equals \(-1\) if \(v\) is the head of \(a\), and equals \(0\) otherwise. Fix a vertex \(y \in V\), and let \(K\) be the matrix obtained from \(M\) by deleting the row indexed by \(y\). Then \(K\) is unimodular: for every injective map \(g\) from an index set into the columns of \(K\), the square submatrix of \(K\) formed by selecting the columns \(g\) (against all remaining rows) has determinant \(0\), \(1\), or \(-1\).

Let \(G\) be a simple graph on a finite vertex set \(V\), and let \((\mathrm{tail}, \mathrm{head})\) be an orientation of \(G\) on a finite arc set \(A\), so that each edge of \(G\) is directed from its tail to its head. Write \(M\) for the oriented incidence matrix of this orientation over \(\mathbb {Z}\), the \(V \times A\) integer matrix whose entry in row \(v\) and column \(a\) is \(1\) if \(v\) is the tail of \(a\), \(-1\) if \(v\) is the head of \(a\), and \(0\) otherwise. Then the graph Laplacian \(L(G)\) of \(G\), taken with integer entries, satisfies

Let \(G\) be a finite simple graph with vertex set \(V\), let \((\mathrm{tail}, \mathrm{head})\) be an orientation of \(G\), and fix a vertex \(y \in V\). Write \(L(G)\) for the integer Laplacian matrix of \(G\) (the vertex degree matrix minus the adjacency matrix), and let \(L(G)_{\widehat{y}}\) denote the reduced Laplacian obtained by deleting the row and the column indexed by \(y\), that is, the submatrix of \(L(G)\) whose rows and columns range over the vertices \(v \neq y\). Then the number of spanning trees \(\tau \) equals the determinant of this reduced Laplacian,

as an identity of integers, for every choice of the deleted vertex \(y\).

Let \(G\) be a finite simple graph on a vertex set \(V\), and let \((\mathrm{tail}, \mathrm{head})\) be an orientation of \(G\) with arc set \(A\), so that \(G\) is the underlying graph of the digraph \((\mathrm{tail}, \mathrm{head})\). Write \(L\) for the graph Laplacian of \(G\) over \(\mathbb {Z}\), the \(V \times V\) matrix whose diagonal entry at \(v\) is the degree of \(v\) and whose off-diagonal entry at \((u,v)\) is \(-1\) when \(u\) and \(v\) are adjacent and \(0\) otherwise. Fix vertices \(i, j \in V\) and a bijection \(e\) between the set of vertices other than \(i\) and the set of vertices other than \(j\), and let \(M\) be the submatrix of \(L\) whose rows are indexed by the vertices \(u \neq i\), whose columns are indexed by the vertices \(u \neq i\) as well, and whose \((u, u')\) entry is \(L_{u,\, e(u')}\). Then the number \(\tau \) of spanning trees of the digraph \((\mathrm{tail}, \mathrm{head})\) satisfies either \(\tau = \det M\) or \(\tau = -\det M\).

Let \(G\) be a finite simple graph, and let \(M\) be its vertex–edge incidence matrix over \(\mathbb {Z}\), whose entry in row \(v\) and column \(e\) is \(1\) when \(v\) is an endpoint of the edge \(e\) and \(0\) otherwise. Then \(M\) is totally unimodular — that is, every square submatrix of \(M\) has determinant \(-1\), \(0\), or \(1\) — if and only if \(G\) is bipartite.

Let \(D\) be a finite digraph with vertex set \(V\) and arc set \(A\), specified by its tail and head maps \(A \to V\), and let \(F\) be a field whose characteristic is a prime \(p\). Writing \(\mathcal{B}\) for the bond space and \(\mathcal{C}\) for the cycle space of \(D\) over \(F\), the intersection \(\mathcal{B} \cap \mathcal{C}\) has positive dimension over \(F\) if and only if \(p\) divides the number \(\tau (D)\) of spanning trees of \(D\).

Let \(K\) be a field and let \(\iota \) be a finite index set, and equip the space of functions \(\iota \to K\) with the standard dot-product bilinear form. Then for all functions \(x, y \colon \iota \to K\), the value of this form at the pair \((x, y)\) is