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’-. This paper proves the following theorem for bipartite graphs: For a bipartite graph G, one of the following alternatives holds: (a) All the cycles of G are even. (b) G has an odd chordless cycle. (c) For every node minimal odd cycle C, there exist four nodes in C inducing a cycle of length four. (d) 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 K3-e as an induced subgraph.
