Proof NP-Complete for $L = \{G, T \mid G \text{ is a graph with a spanning tree isomorphic to } T\}$

Question

$L = \{G, T \mid G \text{ is a graph with a spanning tree isomorphic to } T\}$ and I try to prove it's NP-Completeness. It seems really easy since obviously it is at least as hard as HAM-PATH which is know to be NP-C. However I can't come up with a good reduction. So far I have:

F = "on input G, s, t

1. Construct the spanning tree T by applying breadth first search algorithm to $s$:

   1.1. add $s$ to $T$

   1.2. go through each of the neighbors: if neighbor is not in $T$ -> stop cycle and do bfs(neigbor)

2. Output $G$, $T$.

Any thoughts?

Answer 1

If $G$ has $n$ vertices, you just want to compare to the path $P_{n}$. So you reduce $HP \leq L$, where $HP$ is Hamiltonian Path.

So let $G$ be a graph with a Hamiltonian Path. We construct an instance of $L$ with parameters $(G, P_{n})$. So suppose $G$ has a Hamiltonian Path. As the Hamiltonian path is a path on $n$ vertices, so $P_{n} \subset G$ and $L$ is satisfied. Conversely, suppose $L$ is satisfied. Then there exists a path of length $n$ in $G$, which is a Hamiltonian path. And so the instance of $HP$ is satisfied. The reduction is constant time, as we aren't modifying $G$. Thus, $L \in \mathcal{NP}$-Hard.

Now just provide the polynomial time verification algorithm, and you are done.

Edit: This is too long for a comment, so I will clarify here.

Actually, that is the reduction with detailed steps. Remember that $\mathcal{NP}$ is the class of decision problems where an answer of YES can be verified in polynomial time. So to show $\mathcal{NP}$-Completeness, you need to show the following:
-A polynomial time verification algorithm, given a correct solution.
-A polynomial time reduction $HP \leq_{p} L$

In the reduction portion of the proof, you have to argue:
-Suppose your graph $G$ has a Hamiltonian path. Does that imply an answer of YES to the constructed instance $(G, P_{n})$? That is, does $G$ have a spanning tree isomorphic to $P_{n}$?

-Conversely, suppose the constructed instance $(G, P_{n})$ is satisfied. Does that imply that $G$ has a Hamiltonian path? That is, if $G$ has a spanning tree isomorphic to $P_{n}$, does $G$ have a Hamiltonian path?

Answer 2

A Hamiltonian path is a spanning tree isomorphic to a linear graph.