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.
In a triangle-free graph, a completeness tree must be a Hamiltonian cycle (minus one of its edges). ISGCI says Hamiltonian cycle is NP-complete in triangle-free graphs. Therefore, so is finding a completeness tree (regardless of any restriction on max number of leaves).