Spanning trees with few branch vertices

Research output: Contribution to journalArticlepeer-review


Colleges, School and Institutes


A branch vertex in a tree is a vertex of degree at least three. We prove that, for all s ≥ 1, every connected graph on n vertices with minimum degree at least ((1/(s+3)) + o(1))n contains a spanning tree having at most s branch vertices. Asymptotically, this is best possible and solves, in less general form, a problem of Flandrin, Kaiser, Kužel, Li and Ryjáček, which was originally motivated by an optimization problem in the design of optical networks.

Bibliographic note

19 pages


Original languageEnglish
Pages (from-to)1503–1520
Number of pages18
JournalSIAM Journal on Discrete Mathematics
Issue number3
Publication statusPublished - 22 Aug 2019


  • math.CO, cs.DM, regularity, absorbing, robust subgraphs, spanning trees, optical networks