Odd cycles and matrices with integrality properties

A cycle of a bipartite graph G(V+, V-; E) is odd if its length is 2 (mod 4), even otherwise. An odd cycle C is node minimal if there is no odd cycle C′ of cardinality less than that of C′ such that one of the following holds:C′ ∩V+ ⊂C ∩V+ or C′ ∩V- ⊂C ∩V-. In this paper we prove the following theorem for bipartite graphs: For a bipartite graph G, one of the following alternatives holds:-All the cycles of G are even. -G has an odd chordless cycle. -For every node minimal odd cycle C, there exist four nodes in C inducing a cycle of length four. -An edge (u, v) of G has the property that the removal of u, v and their adjacent nodes disconnects the graph G. To every (0, 1) matrix A we can associate a bipartite graph G(V+, V-; E), where V+ and V- represent respectively the row set and the column set of A and an edge (i,j) belongs to E if and only if aij = 1. The above theorem, applied to the graph G(V+, V-; E) can be used to show several properties of some classes of balanced and perfect matrices. In particular it implies a decomposition theorem for balanced matrices containing a node minimal odd cycle C, having the property that no four nodes of C induce a cycle of length 4. The above theorem also yields a proof of the validity of the Strong Perfect Graph Conjecture for graphs that do not contain K4-e as an induced subgraph. © 1989 North-Holland.