Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|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
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.