Packing T-joins

Definitions and mathematical statement

Let $G=(V,E)$ be a finite loopless undirected multigraph and let $T\subseteq V$ be a nonempty set of even cardinality. A $T$-join is a subset $J\subseteq E$ such that the vertices having odd degree in the spanning subgraph $(V,J)$ are exactly the vertices in $T$. Different edges of a parallel class are distinct available edges. A packing of $T$-joins is a collection of pairwise edge-disjoint $T$-joins; its size is the number of joins, not their total edge count.

For $X\subseteq V$, the edge cut $\delta(X)$ consists of edges with one endpoint in $X$ and the other outside. It is a $T$-cut when $|X\cap T|$ is odd. The conjecture asks whether an absolute constant $C\ge0$ exists such that, for every integer $k\ge1$ and every pair $(G,T)$ for which all $T$-cuts have at least $k$ edges, there is a packing of at least \[ \frac{2k}{3}-C \] $T$-joins. Since the packing size is an integer, the displayed lower bound is interpreted literally, or equivalently with its ceiling.

The constant is independent of the graph, the terminal set, and $k$. The positive cut lower bound ensures that each connected component contains an even number of terminals, so the existence of a single $T$-join is not obstructed by disconnectedness. The target is a uniform additive error, not an error allowed to grow with $k$.

Short English statement

Does a minimum T-cut of size k guarantee at least two-thirds of k edge-disjoint T-joins, up to one universal additive constant?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3197 (OPG-144), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Packing T-joins. Original problem and discussion. http://www.openproblemgarden.org/op/packing_t_joins.