On a Conjecture on Spanning Trees with Few Branch Vertices

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\).