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?



Is the feedback vertex number bounded by the maximum number of leaves in a spanning tree?
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](http://cms.dt.uh.edu/faculty/delavinae/research/DelavinaWaller2009.pdf). 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.


