On a Conjecture on Spanning Trees with Few Branch Vertices

Abstract

A branch vertex of a tree is a vertex of degree at least three. Matsuda, et. al. [7] conjectured that, if $n$ and $k$ are non-negative integers and $G$ is a connected claw-free graph of order $n$, there is either an independent set on $2k+3$ vertices whose degrees add up to at most $n–3$, or a spanning tree with at most $k$ branch vertices. The authors of the conjecture proved it for $k=1$; we prove it for $k=2$.