I would like to verify my proof of this basic statement (also the terminology):
Statement: Given a connected graph $G$, it always contains a spanning tree as a subgraph.
I try to prove this by induction. Let's build a subtree $T_k=(V_k,E_k) < G=(V,E)$ of cardinality $k$ for each $1\le k \le n$, where $n=|G|$. $T_n$ would be than the desired spanning tree.
For $k=1$ just pick a random vertex.
Now fix $1\le k < n$. The set of vertices in $G$ but not in $T_k$ is non-empty, let's call it $V'_k$. Now there must exists an edge between $V'_k$ and $V_k$, otherwise the graph would be disconnected, let's call it $e_k=(\nu,\nu')$, where $\nu' \in V'_k$,$\nu \in V_k$ .
We now consider $T_{k+1}=(V_k \cup\nu', E_k \cup e_k )$. We must show that $T_{k+1}$ does not contain cycles. Note that in $T_{k+1}$ the degree of $\nu'$ is one. Le's suppose that $T_{k+1}$ contained a cycle. Than this must have $\nu'$ along the path (because $T_k$ is itself a tree). But in a cycle the degree of each vertex (and in particular $\nu'$) is at least 2, which is not the case.
Looks fine to me. Maybe write there must exist an edge between a vertex in $V_k'$ and a vertex in $V_k$ because there are no edges between sets just between vertices.