Brush your trees!

Bryant et al. (2014) propose a graph cleaning process and study the corresponding brush number. As their main result they show that the brush number of a tree with ℓℓ leaves is at least ⌊ℓ+12⌋ and at most ⌈ℓ+12⌉. Answering one of their questions, we show that the trees with an even number ℓℓ of leaves and brush number ℓ2 can be recognized efficiently. Furthermore, we provide a simpler proof of their main result.