Number of decycling sets in a 3-regular planar graph

Question

Defintitions: A graph is said to be r-regular if every of its vertex has a degree $r$. A graph is planar if it can be drawn in a plane without any of its edges intersecting each other except at their endpoints. A graph is connected if there exists at least one path between every pair of its vertices. A tree is connected acyclic graph and a forest is a disconnected acyclic graph. A graph G' is an induced subgraph of a graph G if it inherits all edges over a particular vertex subset of G. A decycling set in a graph is a subset of its vertices, deletion of which induces a forest.

Question: Let $S_n$ be the set of all possible 3-regular connected planar graphs on $n$ vertices. Let N(g) be the number of decycling sets which induce a tree(not a forest) in graph $g$. Let $N_n^*$ = $max\{N(g)\ \forall g\in S_n\}$. Give the smallest order function $f(n)$ such that $N_n^* = O(f(n))$. In other words, give a tight upper bound in terms of n, on the number of tree inducing decycling sets in a 3-regular connected planar graph.

A very loose upper bound of course is $2^n$, which is the number of subsets of vertices. However, not all subsets are trees. And not all trees are induced trees. Moreover, 3-regular graphs are much sparser than a complete graph, and connected planar 3-regular graphs is an even smaller subset of 3-regular graphs. Many applications require the enumeration of certain set of objects associated with a graph, such as the number of spanning trees, or the number of cycles(sometimes special cycles such as cycle basis) or the number of cliques etc. It is natural to wonder if the tight upper bound on the number of objects such as induced trees, and that too in a quite restricted class of graphs i.e. 3-regular connected planar graphs is sub-exponential or even polynomial ?

Illustration: The illustration below shows such a tree in a 3-regular planar graph. The vertices that are not part of the tree compose the decycling set.

Answer 1

The tight bound on the number of decycling sets is $2^{\Theta(|V|)}$. Consider the following $3$-regular planar graph.

In the decycling set, for each $i \in \{1,\dotsc,n\}$ choose either $a_i$ or $b_i$. Moreover, choose the vertex $c_n$ in the decycling set. Note that removing these vertices induces a tree on the remaining vertices. Thus, there are $2^{n} = 2^{\Omega(|V|)}$ choices for a decycling set. The upper bound is naturally $2^{O(|V|)}$ for any input graph (as you mentioned in the question as well). Thus, the tight bound is $2^{\Theta(|V|)}$.