[proofplan] We prove total unimodularity by induction on the order of a square submatrix. For a selected square submatrix, each column has at most two nonzero entries, inherited from the distinct tail and head of the corresponding directed arc because the directed graph is loopless. If a column has at most one nonzero entry, [cofactor expansion](/theorems/398) reduces the determinant to a smaller square submatrix. If every column has two nonzero entries, each such column contains one $1$ and one $-1$, so the rows sum to the zero row and the determinant vanishes. [/proofplan] [step:Induct on the order of the selected square submatrix] Let $k \geq 0$, let $R \subset V$ and $C \subset A$ satisfy $|R| = |C| = k$, and fix orderings $R = \{r_1,\dots,r_k\}$ and $C = \{c_1,\dots,c_k\}$. Let $B \in \mathbb{Z}^{k \times k}$ denote the square submatrix $M_{R,C}$, so \begin{align*} B_{ij} = M_{r_i,c_j} \end{align*} for $1 \leq i,j \leq k$. We prove by induction on $k$ that every such $B$ satisfies $\det B \in \{-1,0,1\}$. For $k=0$, the empty determinant is $1$. For $k=1$, the single entry of $B$ is an entry of $M$, hence belongs to $\{-1,0,1\}$, so the claim holds. Assume now that $k \geq 2$ and that every square submatrix of $M$ of order $k-1$ has determinant in $\{-1,0,1\}$. [/step] [step:Reduce by cofactor expansion when a column has at most one nonzero entry] Suppose that some column $j$ of $B$ has at most one nonzero entry. If column $j$ is the zero column, then the determinant is $0$ by multilinearity of the determinant in that column. Otherwise, there is a unique index $i \in \{1,\dots,k\}$ such that $B_{ij} \neq 0$. Since every entry of $M$ belongs to $\{-1,0,1\}$, we have $B_{ij} \in \{-1,1\}$. Let $B^{(i,j)} \in \mathbb{Z}^{(k-1)\times(k-1)}$ denote the matrix obtained from $B$ by deleting row $i$ and column $j$. This matrix is again a square submatrix of $M$, obtained from the row set $R \setminus \{r_i\}$ and the column set $C \setminus \{c_j\}$ with the inherited orderings. Cofactor expansion along column $j$ gives \begin{align*} \det B = (-1)^{i+j} B_{ij} \det B^{(i,j)}. \end{align*} By the induction hypothesis, $\det B^{(i,j)} \in \{-1,0,1\}$. Since $(-1)^{i+j}B_{ij} \in \{-1,1\}$, it follows that $\det B \in \{-1,0,1\}$. [guided] The induction step is designed to remove one row and one column while staying inside the same class of matrices. Suppose column $j$ of $B$ has at most one nonzero entry. First consider the case where column $j$ has no nonzero entries. Then column $j$ is the zero vector in $\mathbb{Z}^k$. Since the determinant is linear in each column, replacing one column by the zero vector makes the determinant equal to $0$. Thus $\det B = 0$, which is one of the allowed values. Now suppose column $j$ has exactly one nonzero entry. Let $i \in \{1,\dots,k\}$ be the unique row index with $B_{ij} \neq 0$. Because $B$ is a submatrix of the incidence matrix $M$, every entry of $B$ is $-1$, $0$, or $1$, so this unique nonzero entry satisfies $B_{ij} \in \{-1,1\}$. Define $B^{(i,j)} \in \mathbb{Z}^{(k-1)\times(k-1)}$ to be the matrix obtained from $B$ by deleting row $i$ and column $j$. This is not an arbitrary smaller matrix: it is exactly the incidence submatrix selected by the row set $R \setminus \{r_i\}$ and the column set $C \setminus \{c_j\}$, with the induced orderings. Therefore the induction hypothesis applies to $B^{(i,j)}$, and gives \begin{align*} \det B^{(i,j)} \in \{-1,0,1\}. \end{align*} Cofactor expansion along column $j$ has only one surviving term, because all entries in that column except $B_{ij}$ are zero. Hence \begin{align*} \det B = (-1)^{i+j} B_{ij} \det B^{(i,j)}. \end{align*} The factor $(-1)^{i+j}B_{ij}$ is either $1$ or $-1$, and multiplying an element of $\{-1,0,1\}$ by $1$ or $-1$ keeps it in $\{-1,0,1\}$. Therefore $\det B \in \{-1,0,1\}$ in this case. [/guided] [/step] [step:Show the determinant vanishes when every column has two nonzero entries] It remains to consider the case where every column of $B$ has two nonzero entries. Since $D$ is loopless, each arc has distinct tail and head. Define the tail map $t: A \to V$ and the head map $h: A \to V$ by declaring $t(a)$ to be the vertex from which $a$ leaves and $h(a)$ to be the vertex into which $a$ enters. Fix a column index $j \in \{1,\dots,k\}$ and let $a = c_j \in A$. In the full incidence matrix $M$, the column indexed by $a$ has value $1$ in row $t(a)$, value $-1$ in row $h(a)$, and value $0$ in every other row. Since column $j$ of $B$ has two nonzero entries and the only possible nonzero rows of the full column are the distinct rows $t(a)$ and $h(a)$, both $t(a)$ and $h(a)$ lie in $R$. Therefore column $j$ of $B$ contains exactly one $1$ and exactly one $-1$. It follows that the sum of the entries in every column of $B$ is $0$. Equivalently, if $s \in \mathbb{Z}^{1 \times k}$ denotes the row vector obtained by summing all rows of $B$, then \begin{align*} s_j = \sum_{i=1}^{k} B_{ij} = 0 \end{align*} for every $j \in \{1,\dots,k\}$, so $s=0$. Thus the rows of $B$ are linearly dependent: their sum is the zero row. Hence $\det B = 0$. [/step] [step:Conclude total unimodularity for the incidence matrix] The two cases cover every square submatrix $B$ of order $k$: either some column has at most one nonzero entry, or every column has two nonzero entries. In both cases, $\det B \in \{-1,0,1\}$. By induction on $k$, every square submatrix of $M$ has determinant in $\{-1,0,1\}$. Therefore $M$ is totally unimodular. [/step]