A CHARACTERIZATION OF SEYMOUR GRAPHS

A connected undirected graph G is called a Seymour graph if the maximu m number of edge disjoint T-cuts is equal to the cardinality of a mini mum T-join for every even subset T of V(G). Several families of graphs have been shown to be subfamilies of Seymour graphs (Seymour J. Comb. Theory B 49 (1990), 189-222; Proc, London Math. Sec. Ser (3) 42 (1981 ), 178-192; Gerards, J. Comb. Theory B 55 (1992), 73-82; Szigeti, (199 3).) In this paper we prove a characterization of Seymour graphs which was conjectured by Sebo and implies the results mentioned above. (C) 1997 John Wiley & Sons, Inc.