{"id":"arxiv/2606.28198","url":"https://arxiv.org/abs/2606.28198","tags":["math.CO"],"score":0,"title":"Extremal graphs with no subgraph admitting $k+1$ edge-disjoint spanning trees","domain":"math.CO","source":"arxiv","authors":["Qinglin Wang","Yingzhi Tian"],"reviews":0,"subject":"math.CO","summary":"A graph $G$ is $τ_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 $τ_k$-maximal graph of order $n$ satisfies $|E(G)|\\leq (k+1)(n-1)-1$. Furthermore, we construct a family of $τ_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 $τ_k$-maximal…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-26","reactions":{}}