Totally unimodular matrix

Summary

A totally unimodular matrix is an integer matrix in which every square submatrix has determinant $0$, $1$ or $-1$. In particular every entry is $0$, $1$ or $-1$. A linear program whose constraint matrix is totally unimodular and whose right-hand side is integral has integral vertices. This explains why many problems on graphs, such as bipartite matching and network flows, can be solved exactly by linear programming.