Prove that the adjacence matrix of a simple graph is totally unimodular...
I know incidence matrices are totally unimodular because in every column there is a 1 and a -1... makes things easier. Any similar property i could use for adjacency matrix?
Any hints/suggestions/solutions...?
A matrix is said to be totally unimodular if the determinant of any square submatrix of a matrix is either $0$ or $\pm1$. Notice that the determinant of the adjacency matrix of a simple graph is not always $0$ or $\pm1$. Rather, $$\det(A(G))=\sum(-1)^{n-c_1(H)-c(H)}2^{c(H)},$$ where the summation is over all spanning elementary subgraphs $H$ of $G$ and $c(H)$ and $c_1(H)$ denote the number of components in a subgraph $H$ which are cycles and edges, respectively. So the statement "adjacency matrix is totally unimodular" is WRONG. For example consider $C_3$, the cycle graph on three vertices. Determinant of its adjacency matrix is $2$.