DefinitionDefinition: Literature-sourcedProof: Not applicableSession-authored (Fable 5 assisted)judge pass (gpt-5.6-terra)audited 2026-08-28

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

An oriented incidence matrix of a finite simple graph

Definition

Let $G = (V, E)$ be a finite simple graph with ordered vertices $V = {v_{i} : i < n} = {v_{0}, \dots, v_{n - 1}}$ and ordered edges $E = {e_{j} : j < m} = {e_{0}, \dots, e_{m - 1}}$ . Choose, for each edge $e_{j} = {u, w}$ , one endpoint as its tail and the other as its head. The resulting $n \times m$ matrix $B = (b_{i j})$ with entries in ${- 1, 0, 1}$ is an oriented incidence matrix of $G$ , where, for $i < n$ and $j < m$ ,

$b_{i j} = {\begin{cases} 1, & if v_{i} is the head of e_{j}, \\ - 1, & if v_{i} is the tail of e_{j}, \\ 0, & if v_{i} \notin e_{j} . \end{cases}$

Each column therefore has exactly one $1$ and one $- 1$ , because every edge of a simple graph has exactly two distinct endpoints. Different choices of orientation change only the signs of columns.

Depends on

Used by

The Laplacian matrix of a finite simple graph Definition
Kirchhoff's matrix-tree theorem Theorem
The Laplacian equals BB^T for every oriented incidence matrix B Theorem
The Laplacian is positive semidefinite and sends the all-ones vector to zero Theorem

Dependency tree · two levels

6 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Richard P. Stanley, MIT 18.314 handout, The Matrix-Tree Theorem (standard reference, not scraped)