Partitioning edge-connectivity

Partitioning edge-connectivity

Definitions and mathematical statement

Let $a,b\geq1$ be integers and let $G=(V,E)$ be a finite undirected loopless multigraph on at least two vertices. Parallel edges are counted separately. For a nonempty proper subset $X\subset V$, write $\delta_G(X)$ for the set of edges having exactly one endpoint in $X$. The graph is $k$-edge-connected when $|\delta_G(X)|\geq k$ for every such $X$; equivalently, deleting fewer than $k$ edges cannot disconnect it.

The question is whether the hypothesis \[ |\delta_G(X)|\geq a+b+2 \qquad(\varnothing\neq X\subsetneq V) \] always permits a partition $E=A\mathbin{\dot\cup}B$ for which $(V,A)$ is $a$-edge-connected and $(V,B)$ is $b$-edge-connected. In terms of the same cuts, the desired simultaneous conditions are \[ |A\cap\delta_G(X)|\geq a,\qquad |B\cap\delta_G(X)|\geq b \qquad(\varnothing\neq X\subsetneq V). \] The two resulting graphs must be spanning: both retain every vertex of $G$. Each original edge belongs to exactly one of them, and the partition has to satisfy every cut constraint at once. It may depend on $G,a,b$.

This asks for an additive connectivity threshold uniform over all orders and edge multiplicities. Having enough edges in each cut separately is only the input condition; the issue is whether their assignments can be coordinated globally. The special simple-graph case follows by restricting the allowed multigraphs.

Short English statement

Can connectivity of at least a+b+2 be split into two spanning edge-disjoint graphs of edge connectivity at least a and b?

Research attempt: tree packing and exact rounding on three vertices

Scope and literature check.

GPT-6 Astra Ultra, 1 October 2026. Edges are distinct resources even when parallel, and both output graphs must contain every vertex. The original problem [S2] asks for an additive threshold. The Nash-Williams spanning-tree theorem [S3] supplies a stronger general threshold, while a direct rounding argument below verifies the stated threshold for graphs with at most three vertices. These are restricted results, not a claimed new general partition theorem.

1. A certified stronger threshold.

Put $s=a+b$. Suppose every nontrivial cut has at least $2s$ edges. For a partition of the vertices into $q\ge2$ nonempty parts, the sum of the $q$ cut sizes is at least $2sq$. Each edge between different parts contributes twice, so there are at least $sq\ge s(q-1)$ such edges. For the one-part partition the requirement is zero. By the spanning-tree packing theorem, $G$ has $s$ edge-disjoint spanning trees. Assign $a$ of them to $A$ and the other $b$ to $B$. Put all remaining edges in either class, for example $A$.

Every nontrivial cut meets each spanning tree. Edge disjointness therefore gives at least $a$ distinct $A$-edges and $b$ distinct $B$-edges across that cut. This proves the required partition under $2(a+b)$-edge-connectivity. In particular, when $a=b=1$, this is exactly the requested threshold four. The theorem is being used as an external result with its partition hypothesis checked, rather than assumed from minimum degree alone.

2. Full target threshold for three vertices.

Let the three edge multiplicities be $m_{12},m_{13},m_{23}$, set $\lambda=a+b+2$, and suppose each vertex cut has size at least $\lambda$. Define \[ p=\frac{a+1}{\lambda},\qquad A_{ij}=\lfloor p m_{ij}\rfloor,\qquad B_{ij}=m_{ij}-A_{ij}. \] Choose that many actual parallel edges for each class. Any nontrivial cut in a three-vertex graph consists of exactly two bundles. If its total multiplicity is $c$, then \[ |A\cap\delta(X)|>pc-2\ge a-1, \qquad |B\cap\delta(X)|\ge(1-p)c\ge b+1. \] The first quantity is an integer, hence is at least $a$; the second is certainly at least $b$. Complementary vertex cuts are the same edge sets, so these checks exhaust all cuts. The construction also allows a bundle of multiplicity zero. On two vertices there is just one bundle: assign any $a$ edges to $A$ and the remainder to $B$. Thus all loopless multigraphs of orders two and three satisfy the conjectured threshold, for every $a,b\ge1$.

3. Why the fractional argument is insufficient in general.

For arbitrary order, assigning fraction $p$ of each edge to $A$ meets every fractional cut constraint, with slack: the $A$-mass is at least $a+1$ and the $B$-mass at least $b+1$. This is not an edge partition. Rounding each parallel bundle down independently loses less than one unit per bundle crossing a cut. A three-vertex cut has only two bundles, which is exactly what made the preceding strict inequality useful. In a large simple graph, a cut may cross arbitrarily many one-edge bundles. Indeed independent rounding with $0<p<1$ assigns zero edges of every such bundle to $A$. Consequently fractional feasibility plus this rounding rule cannot prove the general claim.

Verification and first gap.

The companion script [S4] checks the three-bundle formula using exact integer arithmetic for $1\le a,b\le4$ and all bundle multiplicities between zero and ten satisfying the input cuts. The proof itself is uniform and does not rely on that finite range. The unresolved step is coordinating integral choices across all cuts with only the two units of slack in the original threshold; the tree-packing argument uses greater connectivity and does not supply that coordination.

Final status

UNRESOLVED. The conjecture is verified here for order at most three and for $a=b=1$, and a general stronger threshold is recovered. Completion estimate: no defensible global percentage.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3159 (OPG-146), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Partitioning edge-connectivity. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/partitioning_edge_connectivity.
• S3 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.
• S4 GPT-6 Astra Ultra, reproducible exact checks accompanying this batch, 1 October 2026. Repository file scripts/check_attempt_batch02_connectivity_2026_10_01.py; run with Python 3.