Two-trees optimal \(T\)-join and integral packing of \(T\)-cuts (Q1333320)

Let \(T\) be a subset of the vertex set of an undirected graph \(G= (V,E)\). A subset \(J\) of \(E\) is a \(T\)-join if \(d_ J(v)\) is odd iff \(v\in T\). A cut \((X,V\backslash X)\) is a \(T\)-cut if \(| X\cap T|\) is odd. Assume that \((G,T)\) has an optimal \(T\)-join (a \(T\)-join of minimum cardinality) which is a forest of two trees. The main theorem characterizes the cases where \((G,T)\) has an optimal packing of \(T\)-cuts which is integral. This theorem generalizes a theorem of Seymour on packing of \(T\)-cuts and a theorem of Frank on planar edge disjoint paths. It also solves positively a conjecture by Frank.