# How to prove in a graph $G$, its incidence matrix $A$ is totally unimodular if and only if $G$ is a bipartite graph?

I'm learning network and transportation model. The question is not from my homework. I'm just curious about:

In a graph $G$, its incidence matrix $A$ is totally unimodular if and only if $G$ is a bipartite graph.

Could anyone good at proving give a simple provement?

OR

Could anyone provide some related materials?

-
Most books with "integer programming" in their title will have a proof of this. –  Chris Godsil Nov 13 '12 at 23:49

## 1 Answer

I suppose you refer to undirected graphs, as the (node-arc-) incidence matrix of a directed graph is always totally unimodular.

Anyways, you'll find a nice proof for your question right at the first hit on Google after querying for "incidence matrix bipartite".

-