# Completeness spanning trees

A spanning tree of a graph is called a completeness tree if the set of its leaves induces a complete subgraph in the host graph. Given a graph $G$ and an integer $k$, what is the complexity of deciding if $G$ contains a completeness tree with at most $k$ leaves?

A reason for asking this question is that the corresponding problem for independency trees is NP-complete, here an independency tree is a spanning tree such that the set of its leaves is an independent set in the host graph.

Another reason is this question (and the corresponding answers). It turns out that every spanning tree of $G$ is a completeness tree if and only if $G$ is a complete graph or a cycle.

Let $k \ge 2$ be a fixed interger. Given $G$, construct $H$ as follows:Take two copies $G_1$, $G_2$ and a clique $Q$ on $k$ vertices $x, x_1, x_2, \ldots, x_{k-1}$, a new vertex $y$, fix a vertex $v_1 \in G_1$ and a vertex $v_2 \in G_2$. $H$ is obtained from $G_1, G_2, Q$ and $y$ by joining $x$ to $v_1$, joining $x_1, x_2, \ldots, x_{k-1}$ to $v_2$ and joining all neighbors of $v_1$ in $G_1$ and all neighbor of $v_2$ in $G_2$ to $y$.
Then it can be easily seen that $G$ has a Hamiltonian cycle if and only if $H$ has a completeness tree with at most $k$ leaves.