Jump-systems of T-paths

NEW

Problem: Reconstructed statement: for a finite undirected graph $G=(V,E)$, $T\subseteq V$, and partitions $\mathcal T_1,\mathcal T_2$ of $T$, define

where $d_G(X)=|\delta_G(X)|$. A vector is $\mathcal T_1$-$\mathcal T_2$-feasible if it is realized as endpoint counts of edge-disjoint paths whose two endpoints lie in different blocks of both partitions. The conjecture says that if every vertex degree of $G$ is even, then every vertex of $Q(G,\mathcal T_1)\cap Q(G,\mathcal T_2)$ is $\mathcal T_1$-$\mathcal T_2$-feasible.

Result: The conjecture is false.

Let

and let $G$ have edge set

The degrees are

so all are even. Let

Consider

First, $m\in Q(G,\mathcal T_1)\cap Q(G,\mathcal T_2)$. Indeed, the following fractional $\mathcal T_1$-routing has endpoint-count vector $m$ and edge-load exactly $1$ on every edge:

Similarly, the following fractional $\mathcal T_2$-routing has endpoint-count vector $m$:

Such fractional routings satisfy the defining cut inequalities of $Q$.

Moreover, $m$ is a vertex. At $m$, the following six defining inequalities are tight:

They come respectively from the cuts

These six equations have the unique solution

Hence $m$ is an extreme point of $Q(G,\mathcal T_1)\cap Q(G,\mathcal T_2)$.

Finally, $m$ is not $\mathcal T_1$-$\mathcal T_2$-feasible. The allowed terminal pairs are

The endpoint counts $m$ force one of only two possible demand multisets:

The first is impossible because the cut $\{0,4\}$ has size $2$, but four demanded pairs cross it.

For the second, since $\deg(0)=m_0=2$ and $\deg(4)=m_4=2$, the edge $04$ must itself be the $0$-$4$ path. Thus the $0$-$3$ path starts with $01$, and the $2$-$4$ path ends with $45$. The $0$-$3$ path cannot pass through $2$, since vertex $2$ already must be an endpoint of three other paths and has degree $4$. Hence the $0$-$3$ path must be $0-1-5-3$. Then the $2$-$4$ path must use $25$ and $45$, leaving no unused edge incident with $5$ for the required $2$-$5$ path. Contradiction.

Thus a vertex of $Q(G,\mathcal T_1)\cap Q(G,\mathcal T_2)$ is not feasible.

Citation: This is a counterexample to Conjecture 5 of Sadli--Sebő, “Jump-systems of $T$-paths,” arXiv:2302.13448. No prior published resolution is used here.