1. The unoriented incidence matrix of a bipartite graph, which is the coefficient matrix for bipartite matching, is totally unimodular (TU). (The unoriented incidence matrix of a non-bipartite graph is not TU.) More generally, in the appendix to a paper by Heller and Tompkins, A.J. Hoffman and D. Gale prove the following. Let formula_7 be an "m" by "n" matrix whose rows can be partitioned into two disjoint sets formula_8 and formula_9. Then the following four conditions together are sufficient for "A" to be totally unimodular: