Reduce the
UNDIRECTED HAMILTONIAN CIRCUIT problem to the
SPANNING SUBGRAPH problem.
These problems are defined as follows:
 UNDIRECTED HAMILTONIAN CIRCUIT: given an undirected graph $G$, is
there a cycle that visits each node of $G$ exactly once? In other words, is it
possible to order the nodes of $G$ such that there is an edge between each $2$
contiguous nodes and an edge between the last and the first nodes?
More formally, this problem can be defined as the following set:
$\{ G=\langle V,E\rangle \mid V=\{n_1,\ldots,n_k\}\;\wedge\;\forall i\in\{1,\ldots,k\}: \{n_i,n_{(i\text{ mod }k)+1}\}\in E \}$
 SPANNING SUBGRAPH: given two undirected graphs $G_1$ and $G_2$, is
$G_1$ a spanning subgraph of $G_2$? In other words, can the nodes of $G_1$ and
$G_2$ be bijectively mapped such that if any two nodes $u,v$ of $G_1$ are
connected by an edge in $G_1$ then their corresponding mapped nodes of $G_2$
are connected by an edge in $G_2$?
More formally, this problem can be defined as the following set:
$\{ \langle G_1=\langle V_1,E_1\rangle,\;G_2=\langle V_2,E_2\rangle\rangle \mid \exists M:V_1\to V_2\text{ total and bijective}: \forall u,v\in V_1: (\{u,v\}\in E_1 \Rightarrow \{M(u),M(v)\}\in E_2) \}$
The input and output of the reduction conform to the following data types:

in: struct {
numnodes: int
edges: array of array [2] of int
adjacents: array of array of int
adjacencymatrix: array of array of int
}
The input is an undirected graph. The graph is given by means of four different
kinds of information: the number of nodes in.numnodes, the list of edges
in.edges, for each node the list of its adjacent nodes
in.adjacents, and the adjacency matrix in.adjacencymatrix. The
nodes are integers between $1$ and in.numnodes, and thus, the $0$’th
position of in.adjacents does not contain useful data and should be
ignored; for any other position $p$, in.adjacents[p] is the list of
nodes adjacent to $p$. For the same reason, the $0$’th row and column of
in.adjacencymatrix do not contain useful data and should be ignored; for
any other row $r$ and column $c$, in.adjacencymatrix[r][c] is $0$ when
there is no edge between the nodes $r$ and $c$, and $1$ otherwise.
Note: The input graph has at least $2$ nodes, no repeated edges, nor selfloop edges.

out: struct {
g1edges: array of array [2] of string
g1nodes: array of string
g2edges: array of array [2] of string
g2nodes: array of string
}
The output is a pair of undirected graphs, which are described with their lists
of edges out.g1edges and out.g2edges and with their lists of
nodes out.g1nodes and out.g2nodes, respectively. An edge is a
pair of nodes, and each node is represented by either an integer or a string.
The lists of nodes out.g1nodes and out.g2nodes are optional, and
contain nodes of the graphs, that may or may not appear in the corresponding
list of edges. These lists of nodes could be useful, for example, for including
the nodes that are not connected to any other node, if this is considered
necessary.
Note: If the output graphs have a different number of nodes, then the spanning
subgraph property cannot be satisfied. Selfloop edges are taken into account
to check the property. Repeated edges are ignored.