show/hide this revision's text 2 edited body

This isn't a complete answer, but at least it's a step. I think it should be possible to prove that FVS(G) < 2 MaxLeaf(G).

More specifically, if NonTwo(T) is the number of nodes in spanning tree T that do not have degree two, and MaxNonTwo(G) is the maximum value of NonTwo(T) over all spanning trees of G, then I think that

  • MaxNonTwo(G) < 2 MaxLeaf(G). This is obvious: in any tree, the number of leaves in T is greater than half of NonTwo(G)NonTwo(T), so the tree T that maximizes NonTwo(GNonTwo(T) has greater than NonTwo(G)/2 NonTwo(T)/2 leaves, and the max leaf spanning tree can only have even more leaves.

  • FVS(G) ≤ MaxNonTwo(G). More specifically, in every tree T maximizing NonTwo(T), the set of vertices of degree ≠ 2 form a feedback vertex set. For, if there's a cycle induced by the degree-2 vertices of T, then some edge e of the cycle does not belong to T. If the path in T connecting the endpoints of e passes through a vertex v that does not have degree three, then adding e and removing an edge incident to v produces a tree with a larger value of NonTwo(T). If this situation does not occur, then all edges in the induced cycle are non-tree edges; adding two consecutive edges from the cycle to T and removing two of the edges from T (two of the three edges at the median in T of the endpoints of the added cycle edges) produces a new tree with greater NonTwo again (the three endpoints of the added edges get their degree increased above two, the median goes from degree three to degree one, and two other vertices get their degrees decreased from three to two).
show/hide this revision's text 1

This isn't a complete answer, but at least it's a step. I think it should be possible to prove that FVS(G) < 2 MaxLeaf(G).

More specifically, if NonTwo(T) is the number of nodes in spanning tree T that do not have degree two, and MaxNonTwo(G) is the maximum value of NonTwo(T) over all spanning trees of G, then I think that

  • MaxNonTwo(G) < 2 MaxLeaf(G). This is obvious: in any tree, the number of leaves in T is greater than half of NonTwo(G), so the tree T that maximizes NonTwo(G) has greater than NonTwo(G)/2 leaves, and the max leaf spanning tree can only have even more leaves.

  • FVS(G) ≤ MaxNonTwo(G). More specifically, in every tree T maximizing NonTwo(T), the set of vertices of degree ≠ 2 form a feedback vertex set. For, if there's a cycle induced by the degree-2 vertices of T, then some edge e of the cycle does not belong to T. If the path in T connecting the endpoints of e passes through a vertex v that does not have degree three, then adding e and removing an edge incident to v produces a tree with a larger value of NonTwo(T). If this situation does not occur, then all edges in the induced cycle are non-tree edges; adding two consecutive edges from the cycle to T and removing two of the edges from T (two of the three edges at the median in T of the endpoints of the added cycle edges) produces a new tree with greater NonTwo again (the three endpoints of the added edges get their degree increased above two, the median goes from degree three to degree one, and two other vertices get their degrees decreased from three to two).