Determinant of any squared submatrix of incidence matrix of any graph is 0, $(-2)^i$ or $2^i$?

Question

Why the below proposition is true?

For any graph, determinant of any submatrix of its incidence matrix is 0, $(-2)^i$ or $2^i$. ($i \in \mathbb{Z}$)

Answer 1

The incidence matrix $B$ of a graph has its rows indexed by vertices and columns by edges; its $ij$-entry is 1 if the $i$-th vertex is on the $j$-th edge, otherwise it's 0. In general it is is not square. It is true that the determinant of a square submatrix of the incidence matrix of a graph is $0$ or $\pm 2^k$ for some $k$. It has the important consequence that if $b$ is an integer vector and $Bx=b$, then $2x$ is an integer vector, this plays a role in some combinatorial optimization problems on graphs.

I offer some hints towards a proof. Suppose $M$ is a square submatrix of $B$. If a row or column of $M$ is zero, we're done. Similarly if a row or column has exactly one non-zero entry, by induction. So each column of $M$ must have exactly two non-zero entries. Now you can argue that $M$ must be the incidence matrix of a cycle, and then compute its determinant.