<p>I cannot beat David in the elegance of his answer. But after spending al lot of time on thinking about this problem I 
would like to betray my solution to you though ;)</p>

<p>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$. </p>

<p>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.</p>

CC BY-SA 3.0
2013-09-06T11:12:42.870Z
2013-09-06T11:12:42.870Z
user13136
<p>In a triangle-free graph, a completeness tree must be a Hamiltonian cycle (minus one of its edges). <a href="http://www.graphclasses.org/classes/gc_371.html">ISGCI</a> 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).</p>

CC BY-SA 3.0
2013-09-06T19:21:15.827Z
Oh, this is a nice observation, thank you!
vb le
CC BY-SA 3.0
2013-09-06T07:33:10.290Z
2013-09-06T07:33:10.290Z
David Eppstein
<p>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?</p>

<p>A reason for asking this question is that the corresponding problem for 
<a href="http://www.sciencedirect.com/science/article/pii/S0012365X96003068" rel="nofollow noreferrer">independency trees</a> 
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. </p>

<p>Another reason is <a href="https://mathoverflow.net/questions/140200/on-super-connected-graphs">this question</a> 
(and the corresponding answers). It turns out that <em>every</em> spanning tree of $G$ is a completeness tree 
if and only if $G$ is a complete graph or a cycle.   </p>

<cc.complexity-theory><graph-theory><graph-algorithms>
Completeness spanning trees
vb le
# Completeness spanning trees

(Asked by: username_0 on 2013-09-05)

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](http://www.sciencedirect.com/science/article/pii/S0012365X96003068)
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](https://mathoverflow.net/questions/140200/on-super-connected-graphs)
(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.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms


---

## 2 answers

### Answer by username_2 on 2013-09-06. Score: 12 | Accepted answer

In a triangle-free graph, a completeness tree must be a Hamiltonian cycle (minus one of its edges). [ISGCI](http://www.graphclasses.org/classes/gc_371.html) 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).

> **Comments:**
> **username_0**: Oh, this is a nice observation, thank you!  

---

### Answer by username_1 on 2013-09-06. Score: 8

I cannot beat David in the elegance of his answer. But after spending al lot of time on thinking about this problem I
would like to betray my solution to you though ;)

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.


---

