Skip to content
DraconiticResearch
Search Sources API
181,716 studies31 sourcesUpdated 41 min ago
PreprintarXiv licencearXiv

A Low-Diameter Nash-Williams--Tutte Theorem

  • Pin-Hsian Lee
  • Peng-Ting Lin
  • Meng-Tsung Tsai
  • Ting-An Wu
Open at sourcePDFDOICite

Abstract

The Nash-Williams--Tutte theorem characterizes the existence of k edge-disjoint spanning trees by a condition on every vertex partition. We prove that, for simple graphs, the same condition guarantees k edge-disjoint spanning trees, each of diameter O(n/δ) and with O((n/δ)log(δ+1)) internal vertices, where n is the number of vertices and δ is the minimum degree. Both bounds hold simultaneously for every tree, with absolute implicit constants independent of k, and each is asymptotically optimal in general. Our proof is constructive and yields a randomized algorithm with expected running time Õ(n5). We derive applications to short edge-disjoint routes and weak linkages, small Steiner trees, and survivable networks with short paths. The joint bounds also yield low-diameter spanning Eulerian subgraphs and short tours for postman and general routing problems.

Related

  1. A Tutte-Like Theorem for Injective Flows on Meshes
    Darsh Kaushik, Noam Aigerman
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  2. An Erdős-Pach-Pollack-Tuza theorem for oriented diameter
    Jiangdong Ai, Bin Chen, Yaokun Feng
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. The Tutte polynomial determines the linear coefficient of the Ehrhart polynomial
    Erik Panzer
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Some Early Results by Tutte Regarding the Cycle Double Cover Conjecture in 1948
    Cun-Quan Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. The Tutte embedding of tree-weighted planar maps converges to Liouville quantum gravity
    Nina Holden
    arXivPreprintarXiv licenceFull textAnalysis & PDEsMathematical physicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{lee2026lowdiameter,
  title = {{A Low-Diameter Nash-Williams--Tutte Theorem}},
  author = {Pin-Hsian Lee and Peng-Ting Lin and Meng-Tsung Tsai and Ting-An Wu},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.05043},
  eprint = {2611.05043},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05043},
}
RIS
TY  - UNPB
TI  - A Low-Diameter Nash-Williams--Tutte Theorem
AU  - Pin-Hsian Lee
AU  - Peng-Ting Lin
AU  - Meng-Tsung Tsai
AU  - Ting-An Wu
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.05043
UR  - https://arxiv.org/abs/2611.05043
AB  - The Nash-Williams--Tutte theorem characterizes the existence of k edge-disjoint spanning trees by a condition on every vertex partition. We prove that, for simple graphs, the same condition guarantees k edge-disjoint spanning trees, each of diameter O(n/δ) and with O((n/δ)log(δ+1)) internal vertices, where n is the number of vertices and δ is the minimum degree. Both bounds hold simultaneously for every tree, with absolute implicit constants independent of k, and each is asymptotically optimal in general. Our proof is constructive and yields a randomized algorithm with expected running time Õ(n^5). We derive applications to short edge-disjoint routes and weak linkages, small Steiner trees, and survivable networks with short paths. The joint bounds also yield low-diameter spanning Eulerian subgraphs and short tours for postman and general routing problems.
ER  -