Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Most books with "integer programming" in their title will have a proof of this. – Chris Godsil Nov 13 '12 at 23:49
up vote 1 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.