# Is the feedback vertex number bounded by the maximum number of leaves in a spanning tree?

I have a graph-theoretical conjecture which I think would have been studied before, but for which I cannot find anything in the literature.

Let G be a finite, simple, connected graph. Let the feedback vertex number $FVS(G)$ be the minimum number of vertices that have to be deleted from $G$ to break all cycles, so the minimum number of deletions needed to turn $G$ into a forest. Let the max leaf number $MaxLeaf(G)$ be the maximum number of leaves in any spanning tree for $G$.

My conjecture is that $FVS(G) \leq MaxLeaf(G)$.

The two numbers come close for complete graphs: a $K_t$ has a spanning tree with $(t-1)$ leaves, and $(t-2)$ deletions are needed to turn $K_t$ into a forest. Since a forest can have an arbitrary number of leaves and has FVS number 0, the MaxLeaf number cannot be bounded by a function of the FVS number.

I can prove that $FVS(G) \leq 6 \cdot MaxLeaf(G)$ through a lemma on spanning trees which says that for every connected graph G containing m vertices of degree $\neq 2$, there is a spanning tree for G with at least $m/6$ leaves. Since the deletion of the set of vertices of degree $\neq 2$ turns a graph into a forest if the graph is not a simple cycle, this shows that $FVS(G) \leq 6 \cdot MaxLeaf(G)$ when $G$ is not a simple cycle; and it is easy to see that the claim also holds when $G$ is a simple cycle since $MaxLeaf(C_n) = 2$ and $FVS(C_n) = 1$ for $n \geq 3$.

Since the complement of the leaves in a spanning tree form a connected dominating set, and since the complement of a feedback vertex set is a maximum induced forest, an alternative way to state the conjecture is: For any connected graph $G$ the number of vertices in the largest induced subforest of $G$ is at least as large as the minimum size of a connected dominating set in $G$.

So my question is: is this conjecture true, and does anyone know of any research related to it?

-
You might consider looking at this circle of ideas for planar graphs. David Barnette showed that for a planar 3-connected graph there is always a spanning tree of maximum valence 3. However, if I remember properly, he also showed that for d-polytopal graphs (d more than 3) that there is no uniform upper bound for the valence of a spanning tree. d-polytopal graphs are known to be d-connected. This paper might also be of interest: citeseerx.ist.psu.edu/viewdoc/… –  Joseph Malkevitch Jul 13 '10 at 12:39

Bill Waller and I proved the stronger statement that for G a graph on n(G) > 1 vertices, the order of a largest induced linear forest is at least one plus the connected domination number. See our preprint. A linear forest is a forest in which each connected component is a path, and clearly a lower bound for the order of a largest forest.

-
Excellente, thanks a lot! I actually looked at the preprint briefly during my web search, but missed the theorem. Nice work. –  Bart Jansen Jul 13 '10 at 21:43