Indecomposable r-graphs and some other counterexamples

An r-graph is any graph that can be obtained as a conic combination of its own 1-factors. An r-graph G(V, E) is said to be indecomposable when its edg e set E cannot be partitioned as E = E-1 boolean OR E-2 so that G(i)(V, E-i ) is an r(i)-graph for i = 1,2 and, for some r(1), r(2). We give an indecom posable r-graph for every integer r greater than or equal to 4. This answer s a question raised in [Seymour, Proc London Math Soc 38 (1979, 423-460], a nd has interesting consequences for the Schrijver System of the T-cut polyh edron to be given in [Rizzi, 1997, to appear]. A graph in which every two 1 -factors intersect is said to be poorly matchable. Every poorly matchable r -graph is indecomposable. We show that for every r greater than or equal to 4 that "being indecomposable" does not imply "being poorly matchable." Nex t we give a poorly matchable r-graph for every r greater than or equal to 4 . The article provides counterexamples to some conjectures of Seymour. (C) 1999 John Wiley & Sons, Inc.