Extremal graphs with no subgraph admitting $k+1$ edge-disjoint spanning trees

Qinglin Wang; Yingzhi Tian

arxiv: 2606.28198 · v1 · pith:Z4LZLQG2new · submitted 2026-06-26 · 🧮 math.CO

Extremal graphs with no subgraph admitting k+1 edge-disjoint spanning trees

Qinglin Wang , Yingzhi Tian This is my paper

Pith reviewed 2026-06-29 03:12 UTC · model grok-4.3

classification 🧮 math.CO

keywords τ_k-maximal graphsedge-disjoint spanning treesextremal graphsedge boundsspanning tree packingmaximal graphsgraph theory

0 comments

The pith

Every τ_k-maximal graph on n≥2k+2 vertices has at most (k+1)(n-1)-1 edges.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies τ_k-maximal graphs, which contain no subgraph admitting k+1 edge-disjoint spanning trees, but become such a graph upon addition of any missing edge. It proves an upper bound of (k+1)(n-1)-1 edges on any such graph when the order n is at least 2k+2. Constructions are given that meet this bound exactly, establishing sharpness. The authors conjecture that every τ_k-maximal graph attains precisely this edge count and confirm the conjecture in the case k=1.

Core claim

For any integers k≥1 and n≥2k+2, every τ_k-maximal graph G of order n satisfies |E(G)|≤(k+1)(n-1)−1. Furthermore, there exists a family of τ_k-maximal graphs on n≥2k+2 vertices with exactly (k+1)(n-1)−1 edges. The paper conjectures that equality always holds and verifies this for k=1.

What carries the argument

The τ_k-maximality condition: no subgraph admits k+1 edge-disjoint spanning trees, yet every added edge creates one.

If this is right

The number of edges in any τ_k-maximal graph is bounded above by (k+1)(n-1)-1.
The bound is tight because explicit constructions achieve equality.
When k=1 every τ_1-maximal graph has exactly 2(n-1)-1 edges.
The result supplies the extremal function for the maximum edges in graphs that are maximal with respect to the property of having no subgraph with packing number k+1 for spanning trees.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the conjecture is true, then the edge count of every τ_k-maximal graph is determined exactly by the formula (k+1)(n-1)-1.
The constructions may be checked directly for small values of k>1 to test whether fewer edges can occur.
The bound suggests a connection to the minimum number of edges that forces a subgraph whose arboricity exceeds k.

Load-bearing premise

The maximality condition in the definition of τ_k-maximal, together with n≥2k+2, is enough to force the edge upper bound.

What would settle it

Exhibiting a τ_k-maximal graph on n=2k+2 vertices with more than (k+1)(2k+1)-1 edges would disprove the claimed upper bound.

Figures

Figures reproduced from arXiv: 2606.28198 by Qinglin Wang, Yingzhi Tian.

**Figure 3.** Figure 3: Structure for Case 3 of Lemma 2.5 u v1 v2 v3 u1 w1 u2 w2 e0 f L1 L L2 00 L 0 L [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

read the original abstract

A graph $G$ is $\tau_k$-maximal if $G$ contains no subgraph admitting $k+1$ edge-disjoint spanning trees, while the addition of any edge in the complement of $G$ yields a subgraph that admits $k+1$ edge-disjoint spanning trees. In this paper, we prove that for any integers $k\geq 1$ and $n\geq 2k+2$, every $\tau_k$-maximal graph of order $n$ satisfies $|E(G)|\leq (k+1)(n-1)-1$. Furthermore, we construct a family of $\tau_k$-maximal graphs on $n\ge 2k+2$ vertices that have exactly $(k+1)(n-1)-1$ edges, which establishes the tightness of the upper bound. Then we conjecture that every $\tau_k$-maximal graph on $n$ vertices has exactly $(k+1)(n-1)-1$ edges, and we verify the conjecture for the case $k=1$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines τ_k-maximal graphs and proves a tight upper bound of (k+1)(n-1)-1 edges for n ≥ 2k+2, with matching constructions and the k=1 case settled.

read the letter

The main takeaway is that τ_k-maximal graphs—those without any subgraph packing k+1 edge-disjoint spanning trees, but maximal with respect to adding any missing edge—satisfy |E(G)| ≤ (k+1)(n-1)-1 when n ≥ 2k+2, and the authors give an explicit family hitting equality. They also conjecture that every such graph meets the bound exactly and confirm it for k=1.

The new element is the τ_k-maximal definition itself, which layers a maximality condition on top of the usual forbidden-subgraph setup from spanning-tree packing. The bound is derived by showing that more edges would force either a forbidden subgraph or a violation of maximality, and the constructions appear to be built from a core that packs k trees plus a controlled number of extra edges. The k=1 verification is direct and gives a useful sanity check.

The constructions are a clear strength; explicit examples that achieve the bound make the result sharper. The size restriction n ≥ 2k+2 is stated up front, so the scope is clear.

The open conjecture for k > 1 is the obvious soft spot—the paper stops short of a full characterization. The proof steps themselves look internally consistent from the abstract and stress-test description, with no circularity or hidden parameters. No load-bearing gaps are apparent.

This is aimed at combinatorialists working on extremal problems tied to connectivity or tree packing. Anyone already following Nash-Williams-type results or forbidden configurations in graphs would get value from the new notion and the matching bound. It is solid enough to warrant peer review.

Referee Report

0 major / 2 minor

Summary. The paper defines a graph G as τ_k-maximal if it contains no subgraph admitting k+1 edge-disjoint spanning trees, yet adding any edge from the complement produces such a subgraph. It proves that for integers k≥1 and n≥2k+2, every τ_k-maximal graph on n vertices satisfies |E(G)|≤(k+1)(n-1)−1. It also constructs an explicit family of τ_k-maximal graphs on n≥2k+2 vertices achieving exactly (k+1)(n-1)−1 edges. The paper conjectures that every τ_k-maximal graph has precisely this number of edges and verifies the conjecture for k=1.

Significance. If the proof and constructions hold, the work determines the maximum number of edges in τ_k-maximal graphs and exhibits matching examples, thereby establishing the extremal function for this maximality condition. The explicit constructions demonstrate tightness directly, and the k=1 verification provides a concrete check of the conjecture. This contributes a precise structural result in extremal graph theory concerning forbidden subgraphs defined via spanning-tree packings.

minor comments (2)

[Abstract] The abstract states the main theorem and construction but does not indicate the proof technique (e.g., whether it proceeds by contradiction on the number of edges or by induction on n); adding one sentence would improve readability.
The conjecture is stated after the main results; a brief remark on why the authors expect equality to hold in general (beyond the k=1 case) would help readers assess its plausibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript and the recommendation to accept. The referee's summary accurately describes the definition of τ_k-maximal graphs, the upper bound on the number of edges, the matching constructions, and the conjecture (with the k=1 case verified).

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper proves the edge upper bound directly from the definition of τ_k-maximal (no subgraph with k+1 edge-disjoint spanning trees, but any added edge creates one) together with n ≥ 2k+2, by contradiction on exceeding the bound. It then gives an explicit construction achieving equality. The k=1 case is verified separately and directly. No self-definitional steps, no fitted inputs renamed as predictions, and no load-bearing self-citations or imported uniqueness theorems appear in the derivation chain. The conjecture is stated as open and separate from the proved result. The argument is self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard graph-theoretic definitions and the characterization of graphs admitting k+1 edge-disjoint spanning trees.

axioms (2)

standard math Standard axioms of graph theory: subgraphs, spanning trees, edge-disjointness, and maximality under edge addition.
Invoked throughout the definition of τ_k-maximal graphs.
domain assumption Nash-Williams-Tutte theorem characterizing the maximum number of edge-disjoint spanning trees via minimum cut densities over partitions.
Implicitly required to equate the forbidden property with a concrete numerical condition on edge cuts.

pith-pipeline@v0.9.1-grok · 5714 in / 1474 out tokens · 74770 ms · 2026-06-29T03:12:27.603679+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references

[1]

J. A. Bondy, U. S. R. Murty,Graph Theory, Springer, New York, 2008

2008
[2]

P. A. Catlin,A reduction method to find spanning Eulerian subgraphs, Journal of Graph Theory12(1) (1988) 29–44

1988
[3]

Gusfield,Connectivity and edge-disjoint spanning trees, Information Processing Letters 16(2) (1983) 87–89

D. Gusfield,Connectivity and edge-disjoint spanning trees, Information Processing Letters 16(2) (1983) 87–89. 12

1983
[4]

Harary,The maximum connectivity of a graph, Proceedings of the National Academy of Sciences48(7) (1962) 1142–1146

F. Harary,The maximum connectivity of a graph, Proceedings of the National Academy of Sciences48(7) (1962) 1142–1146

1962
[5]

A. Itai, M. Rodeh,The multi-tree approach to reliability in distributed networks, Information and Computation79(1) (1988) 43–59

1988
[6]

Kundu,Bounds on the number of disjoint spanning trees, Journal of Combinatorial Theory, Series B17(2) (1974) 199–203

S. Kundu,Bounds on the number of disjoint spanning trees, Journal of Combinatorial Theory, Series B17(2) (1974) 199–203

1974
[7]

H.-J. Lai, R. Xu, C.-Q. Zhang,On circular flows of graphs, Combinatorica27(2007) 245– 246

2007
[8]

Q. H. Liu, X. H. Huang, Z. Zhang,Restricted edge connectivity of Harary graphs, in: W. F. Wang, X. D. Zhu, D.-Z. Du (eds.), Combinatorial Optimization and Applications. COCOA
[9]

Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, pp. 113–125
[10]

C. St. J. A. Nash-Williams,Edge-disjoint spanning trees of finite graphs, The Journal of the London Mathematical Society36(1961) 445–450

1961
[11]

E. M. Palmer,On the spanning tree packing number of a graph: a survey, Discrete Mathe- matics230(2001) 13–21

2001
[12]

Plesn´ ık,Critical graphs of given diameter, Acta Facultatis Rerum Naturalium Universi- tatis Comenianae

J. Plesn´ ık,Critical graphs of given diameter, Acta Facultatis Rerum Naturalium Universi- tatis Comenianae. Mathematica30(1975) 71–93

1975
[13]

Tay,Rigidity of multi-graphs

T.-S. Tay,Rigidity of multi-graphs. I. Linking rigid bodies inn-space, Journal of Combina- torial Theory, Series B36(1) (1984) 95–112

1984
[14]

W. T. Tutte,On the problem of decomposing a graph intonconnected factors, The Journal of the London Mathematical Society36(1) (1961) 221–230. 13

1961

[1] [1]

J. A. Bondy, U. S. R. Murty,Graph Theory, Springer, New York, 2008

2008

[2] [2]

P. A. Catlin,A reduction method to find spanning Eulerian subgraphs, Journal of Graph Theory12(1) (1988) 29–44

1988

[3] [3]

Gusfield,Connectivity and edge-disjoint spanning trees, Information Processing Letters 16(2) (1983) 87–89

D. Gusfield,Connectivity and edge-disjoint spanning trees, Information Processing Letters 16(2) (1983) 87–89. 12

1983

[4] [4]

Harary,The maximum connectivity of a graph, Proceedings of the National Academy of Sciences48(7) (1962) 1142–1146

F. Harary,The maximum connectivity of a graph, Proceedings of the National Academy of Sciences48(7) (1962) 1142–1146

1962

[5] [5]

A. Itai, M. Rodeh,The multi-tree approach to reliability in distributed networks, Information and Computation79(1) (1988) 43–59

1988

[6] [6]

Kundu,Bounds on the number of disjoint spanning trees, Journal of Combinatorial Theory, Series B17(2) (1974) 199–203

S. Kundu,Bounds on the number of disjoint spanning trees, Journal of Combinatorial Theory, Series B17(2) (1974) 199–203

1974

[7] [7]

H.-J. Lai, R. Xu, C.-Q. Zhang,On circular flows of graphs, Combinatorica27(2007) 245– 246

2007

[8] [8]

Q. H. Liu, X. H. Huang, Z. Zhang,Restricted edge connectivity of Harary graphs, in: W. F. Wang, X. D. Zhu, D.-Z. Du (eds.), Combinatorial Optimization and Applications. COCOA

[9] [9]

Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, pp. 113–125

[10] [10]

C. St. J. A. Nash-Williams,Edge-disjoint spanning trees of finite graphs, The Journal of the London Mathematical Society36(1961) 445–450

1961

[11] [11]

E. M. Palmer,On the spanning tree packing number of a graph: a survey, Discrete Mathe- matics230(2001) 13–21

2001

[12] [12]

Plesn´ ık,Critical graphs of given diameter, Acta Facultatis Rerum Naturalium Universi- tatis Comenianae

J. Plesn´ ık,Critical graphs of given diameter, Acta Facultatis Rerum Naturalium Universi- tatis Comenianae. Mathematica30(1975) 71–93

1975

[13] [13]

Tay,Rigidity of multi-graphs

T.-S. Tay,Rigidity of multi-graphs. I. Linking rigid bodies inn-space, Journal of Combina- torial Theory, Series B36(1) (1984) 95–112

1984

[14] [14]

W. T. Tutte,On the problem of decomposing a graph intonconnected factors, The Journal of the London Mathematical Society36(1) (1961) 221–230. 13

1961