5
$\begingroup$

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?

$\endgroup$
1
  • 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

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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