Consider the following algorithm: We are given a planar graph $G$. We initialise a set of vertices $S$ to an empty set. We randomly pick a vertex $v$ in $G$ and insert it in $S$. Now we keep including in $S$ vertices from the neighbourhood of $S$ such that the vertex we include is adjacent to exactly one vertex in $S$. We stop expanding $S$ when there is no vertex in the neighbourhood of $S$ which is adjacent to exactly one vertex in $S$. Just like BFS produces a breath first tree and DFS produces a depth first tree, the "one neighbourhood" search above also produces a tree. Give a tight upper bound on the number of such trees in $G$.
I expect the number of such trees to be asymptotically lower than O($2^n$), where $n$ is the number of vertices in $G$.