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.   
Completeness spanning trees
cc.complexity theory;graph theory;graph algorithms
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).