When is the adjacency matrix of a simple undirected graph totally unimodular? I would like to know the graphs for which the (node-node) adjacency matrix is totally unimodular. Is the following true?
The adjacency matrix of G is totally unimodular if and only if G is a tree.
 A: EDIT: See Akbari and Kirkland, On unimodular graphs, Linear Algebra and its Applications, Volume 421, Issue 1, 1 February 2007, Pages 3-15. According to the abstract, "Graphs whose adjacency matrices are totally unimodular are also characterized."
Ignore what follows, left here for historical reasons:
Wikipedia says, "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.)"
A: Every tree has a totally unimodular adjacency matrix, but the converse is not true. The matrix $\begin{pmatrix}0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0\end{pmatrix}$ is totally unimodular, but the graph it represents is not a tree.
More generally, a graph has a totally unimodular adjacency matrix if and only if it can be written in the form $\begin{pmatrix}0 & B \\ B^T & 0\end{pmatrix}$ where $B$ is a totally unimodular matrix whose entries are zeros and/or ones.
