# Number of maximal induced trees in a connected planar graph

An induced subgraph $$G’$$ of a graph $$G$$ is a subset of its vertices along with all the edges that are present in $$G$$ among those vertices. For $$G’$$ to be a tree, all vertices of a cycle in $$G$$ cannot be in $$G’$$. The tree composed of bold edges in the illustration given below shows an induced tree $$T$$. Vertex $$u$$ cannot be included in $$T$$ because u brings with itself edges $$(u, v)$$ and $$(u, w)$$ which completes a cycle $$u-v-w-u$$ and $$T$$ no longer remains a tree. $$T$$ is also a maximal induced tree because no more vertices can be included in $$T$$ without violating it being a tree.

The question is, what is a tight upper bound on the number of maximal induced trees in a connected triangulated planar graph. • This is similar to a question I have posted earlier. link Oct 2 at 14:45

Consider the following planar triangulated graph $$G$$. There are $$n+2$$ vertices: $$\{x,y,u_1,\dotsc,u_n,v_1,\dotsc,v_n\}$$. The edge set is $$\{(x,y),(x,u_1),\dotsc,(x,u_n),(y,v_1),\dotsc,(y,v_n),(u_1,v_1),\dotsc,(u_n,v_n),(u_1,u_2),\dotsc,(u_{n-1},u_n),(v_1,v_2),\dotsc,(v_{n-1},v_n), (y,u_1),(v_1,u_2),\dotsc,(v_{n-1},u_n)\}$$.
Suppose your algorithm initially picks $$x$$ and $$y$$ in $$S$$. Thereafter, suppose the algorithm picks the even numbered vertices $$u_{2i}$$ and $$v_{2i}$$ for $$i \in \{1,\dotsc,\lfloor n/2 \rfloor\}$$. Then, the algorithm can construct $$2^{\lfloor n/2 \rfloor}$$ possible induced trees depending on whether $$u_{2i}$$ or $$v_{2i}$$ is included in the induced tree for each $$i \in \{1,\dotsc,\lfloor n/2 \rfloor\}$$. Therefore, there are $$2^{\Omega(|V|)}$$ possible induced trees for this graph. Note that this is asymptotically tight bound in the exponent since in a planar graph, the number of edges are linearly bounded by the number of vertices, i.e., $$|E| = O(|V|)$$ (see here for the properties of a planar graph). Therefore, the number of subgraphs of any planar graph are at most $$2^{O(|V|)}$$.