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?


Could anyone provide some related materials?

  • 1
    $\begingroup$ Most books with "integer programming" in their title will have a proof of this. $\endgroup$ Nov 13, 2012 at 23:49

1 Answer 1


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".


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .