gpt 6 astra ultra attempt on Math-1071

Kriesell's Conjecture

Definitions and mathematical statement

Let $G=(V,E)$ be a finite undirected loopless multigraph, let $T\subseteq V$ be a set of terminals with $|T|\geq2$, and let $k\geq1$ be an integer. Distinct parallel edges remain distinct resources. Paths are edge-disjoint when no edge occurs in two of them; they may share intermediate vertices.

Assume that for each pair of distinct terminals $u,v\in T$ there are $2k$ pairwise edge-disjoint paths from $u$ to $v$ in $G$. The paths witnessing different terminal pairs need not be chosen compatibly. Equivalently, every cut $\delta_G(X)$ with both $X\cap T$ and $T\setminus X$ nonempty has size at least $2k$.

A $T$-Steiner tree is a connected acyclic subgraph of $G$ whose vertex set contains all of $T$. It may also contain other vertices and need not span $G$. Kriesell's conjecture asserts that under the stated hypothesis there exist trees $F_1,\ldots,F_k$ satisfying \[ T\subseteq V(F_i)\quad(1\leq i\leq k),\qquad E(F_i)\cap E(F_j)=\varnothing\quad(i\neq j). \] Only edge disjointness is demanded: terminals and other vertices may be shared among trees. The bound concerns cuts separating terminals, not all cuts of $G$, so parts containing no terminal may have small edge connectivity. For a single terminal the assertion has the harmless interpretation of $k$ copies of its one-vertex tree with empty edge sets.

Short English statement

If every pair of terminals has 2k edge-disjoint connecting paths, must there be k edge-disjoint trees each connecting all terminals?

Research attempt: terminal reductions and a greedy obstruction

Scope, literature, and approach.

GPT-6 Astra Ultra, 1 October 2026. Only cuts separating terminals are controlled; nonterminal vertices need not belong to the output trees. DeVos, McDonald and Pivotto [S3] prove a sufficient terminal connectivity of $5k+4$. This is useful context but does not provide the desired $2k$ threshold. The present work isolates cases where spanning-tree packing applies and checks exactly which elementary reductions preserve the terminal problem.

1. Two immediate exact cases.

For $k=1$, all terminals lie in one connected component. Take finitely many connecting paths from one terminal to every other terminal, choose a spanning tree of their union, and prune leaves outside $T$. The result is a $T$-Steiner tree. If $|T|=2$, the hypothesis supplies $2k$ edge-disjoint paths between the two terminals. Any $k$ of those paths are already the requested trees. Shared intermediate vertices cause no difficulty, because the target asks for edge disjointness.

When $T=V(G)$, every cut is a terminal cut. A partition into $q\ge2$ nonempty parts has at least $kq\ge k(q-1)$ crossing edges, by summing its cut sizes and dividing by two. The Nash-Williams theorem [S4] therefore gives $k$ edge-disjoint spanning trees. This proves the full claimed threshold when every vertex is a terminal.

2. Suppressing a nonterminal of degree two.

Let $v\notin T$ have exactly two incident edges, $uv$ and $vw$, with $u\ne w$. Delete $v$ and replace these two edges by a new labelled edge $uw$, allowing parallel edges. A simple path between terminals that uses $v$ must use both incident edges; replace that segment by the new edge. Edge-disjoint terminal paths remain edge-disjoint, since at most one path in such a family could use either incident edge. Conversely, replacing the new edge by $u,v,w$ lifts terminal paths without identifying edge resources. Thus every pairwise terminal edge connectivity is preserved exactly.

A packing of Steiner trees in the reduced graph also lifts: the unique tree, if any, using the new edge has that edge subdivided by $v$. Subdivision preserves being a tree, and no other lifted tree uses either new segment. Nonterminal leaves and their edges can be deleted as well, since no simple terminal-to-terminal path needs them. These operations give safe reductions, but leave branching nonterminal vertices untouched. No assertion that all such vertices can be suppressed safely is made.

3. Why arbitrary greedy tree deletion fails.

Consider $G=K_5$, take $T=V(G)$, and set $k=2$. Every cut has size at least four, so this instance satisfies the desired hypothesis and is already covered by the spanning-tree theorem. Nevertheless, selecting the spanning star centred at vertex $0$ as the first tree consumes all four edges incident with $0$. The residual graph cannot contain a tree spanning $T$. Thus even an input with no Steiner vertices shows that an arbitrary first tree need not leave a feasible residual instance. Existence of a packing does not authorize a greedy induction using an unrestricted first choice.

More generally, a partition whose every part meets $T$ has at least $kq$ crossing edges by the terminal-cut hypothesis. The spanning-tree theorem, however, requires its inequality for every partition, including parts containing no terminal. Such parts can have very small boundaries. Demanding spanning trees before eliminating them therefore changes the problem and cannot justify the general reduction.

Verification and first remaining gap.

The script [S5] checks all cuts of the $K_5$ example and verifies the isolated centre after star deletion. The degree-two argument tracks labelled edges explicitly, so parallel edges and shared vertices do not conceal a resource conflict. What is missing is a simultaneous choice or splitting procedure at branching nonterminals that preserves all relevant terminal cuts and allows $k$ compatible trees. The easy path reductions do not establish such a procedure.

Final status

UNRESOLVED. Exact elementary cases and safe reductions are proved; the stated greedy shortcut is disproved. The full $2k$ terminal threshold is not established. Completion estimate: no defensible global percentage.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3160 (OPG-56233), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Kriesell's Conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/kriesells_conjecture.
• S3 M. DeVos, J. McDonald and I. Pivotto, Packing Steiner Trees, author preprint $2013$. Checked 1 October 2026. https://arxiv.org/abs/1307.7621.
• S4 C. St. J. A. Nash-Williams, Edge-Disjoint Spanning Trees of Finite Graphs, Journal of the London Mathematical Society 36 $1961$, 445--450. Checked 1 October 2026. https://doi.org/10.1112/jlms/s1-36.1.445.
• S5 GPT-6 Astra Ultra, exact verification script, 1 October 2026: scripts/check_attempt_batch02_connectivity_2026_10_01.py in this repository; run with Python 3.