Lau's Extension Theorem

Let GG be a loopless multigraph, with S,RV(G)S,R\subseteq V(G) such that SR=S\cap R=\emptyset, SS is QkQk-edge-connected, and every rRr\in R has degree at least QkQk, where Q30Q\geq 30. Given a vertex vv and a subpartition Pk(v)P_k(v) of E(v)E(v) into kk parts, an SS-subgraph extends vv when it satisfies the extension condition associated with the subpartition at vv; a collection of subgraphs balances SRS\cup R when their induced edge subpartitions are balanced at every vertex in SRS\cup R.

Lau's Extension Theorem. There are kk edge-disjoint SS-subgraphs that extend vv and balance SRS\cup R if either vSv\in S, d(v)=Qkd(v)=Qk, and Pk(v)P_k(v) is a balanced edge subpartition of E(v)E(v), or N(v)SRN(v)\subseteq S\cup R, d(v)Qkd(v)\leq Qk, vSRv\notin S\cup R, and there is no edge cut of size at most QkQk that breaks GG into C1,C2C_1,C_2 with SC2S\subseteq C_2, vC1v\in C_1, and RC1R\cap C_1\neq\emptyset.

The paper states that this theorem was used in Lau's proof of the 30k30k bound for Steiner forest packing, but identifies a mistake in it and provides a counterexample. Thus the asserted theorem is refuted as stated; the paper's corrected argument instead yields a 36k36k bound, improved to 35k35k when k8k\geq 8.

Sources & referencesView supporting material

Primary source

Jinghan A Zeng, “On the Extension Theorem for Packing Steiner Forests”, arXiv:2603.16956 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.