Spanning trees with leaf distance at least four

For a graph G , we denote by i ( G ) the number of isolated vertices of G . We prove that for a connected graph G of order at least five, if i ( G – S ) < | S | for all ∅ ≠ S ⊆ V ( G ), then G has a spanning tree T such that the distance in T between any two leaves of T is at least four. This result was conjectured by Kaneko in “ Spanning trees with constrains on the leaf degree ”, Discrete Applied Math, 115 (2001), 73–76. Moreover, the condition in the result is sharp in a sense that the condition i ( G – S ) < | S | cannot be replaced by i ( G – S ) ≤ | S |. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 83–90, 2007