Given a connected undirected graph $G$ with vertex set $V$ and edge set $E$. Prove that we can partition the vertices into two sets $V_1,V_2$ and choose a subset of edges $E_0\subseteq E$ so that
No edge of $E$ connects two vertices of $V_1$.
Any edge of $E_0$ connects a vertex in $V_1$ to a vertex in $V_2$.
Any two vertices are connected by a path with edges of $E_0$.
A possible approach is induction. The base case with one vertex is trivially true. If we remove a vertex $v$ from our graph, then we can choose $E_0,V_1,V_2$ for the remaining vertices satisfying our properties. If there exists an edge of $E$ connecting $v$ to a vertex in $V_1$, then we are forced to include $v$ in $V_2$. We can then add any edge connecting $v$ to a vertex in $V_1$ into $E_0$. This almost works, the only problem being if all edges adjacent to $v$ join $v$ with vertices in $V_2$, in which case the connectivity of $E_0$ cannot be guaranteed.