  In this paper, we introduce a new problem called Tree-Residue Vertex-Breaking
(TRVB): given a multigraph $G$ some of whose vertices are marked "breakable,"
is it possible to convert $G$ into a tree via a sequence of "vertex-breaking"
operations (replacing a degree-$k$ breakable vertex by $k$ degree-$1$ vertices,
disconnecting the $k$ incident edges)?
  We characterize the computational complexity of TRVB with any combination of
the following additional constraints: $G$ must be planar, $G$ must be a simple
graph, the degree of every breakable vertex must belong to an allowed list $B$,
and the degree of every unbreakable vertex must belong to an allowed list $U$.
The two results which we expect to be most generally applicable are that (1)
TRVB is polynomially solvable when breakable vertices are restricted to have
degree at most $3$; and (2) for any $k \ge 4$, TRVB is NP-complete when the
given multigraph is restricted to be planar and to consist entirely of
degree-$k$ breakable vertices. To demonstrate the use of TRVB, we give a simple
proof of the known result that Hamiltonicity in max-degree-$3$ square grid
graphs is NP-hard.
  We also demonstrate a connection between TRVB and the Hypergraph Spanning
Tree problem. This connection allows us to show that the Hypergraph Spanning
Tree problem in $k$-uniform $2$-regular hypergraphs is NP-complete for any $k
\ge 4$, even when the incidence graph of the hypergraph is planar.
