A characterization of minimal non-Seymour graphs

A connected undirected graph GG is a Seymour graph if the maximum number of edge disjoint TT-cuts is equal to the cardinality of a minimum TT-join for every even subset TT of V(G)V(G). Ageev, Kostochka, and Szigeti characterized Seymour graphs in 1997. In this paper, we characterize minimal non-Seymour graphs. More precisely, we show that minimal non-Seymour graphs can be completely described by two infinite families of graphs, and we provide a procedure to construct them. Our characterization also generalizes a theorem of Lovász concerning minimal nonbipartite matching-covered graphs.