Packing odd T ‐joins with at most two terminals

Take a graph G , an edge subset Σ ⊆ E ( G ) , and a set of terminals T ⊆ V ( G ) where | T | is even. The triple ( G , Σ , T ) is called a signed graft . A T ‐join is odd if it contains an odd number of edges from Σ. Let ν be the maximum number of edge‐disjoint odd T ‐joins. A signature is a set of the form Σ ▵ δ ( U ) where U ⊆ V ( G ) and | U ∩ T | is even. Let τ be the minimum cardinality a T ‐cut or a signature can achieve. Then ν ≤ τ and we say that ( G , Σ , T )packs if equality holds here. We prove that ( G , Σ , T ) packs if the signed graft is Eulerian and it excludes two special nonpacking minors. Our result confirms the Cycling Conjecture for the class of clutters of odd T ‐joins with at most two terminals. Corollaries of this result include, the characterizations of weakly and evenly bipartite graphs, packing two‐commodity paths, packing T ‐joins with at most four terminals, and a new result on covering edges with cuts.