Partition of vertices and subset of edges 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.
 A: Pick a vertex $v$ and put it into $V_1$.  Add all the edges incident to $v$ to $E_0$ and all the vertices connected to $v$ to $V_2$.
If the residual graph is nonempty, there's at least one edge in $E$ connecting some vertex $w$ in it to some vertex in $V_2$.  Since by construction all edges incident to vertices in $V_1$ have their other endpoints in $V_2$, no edge in $E$ may connect $w$ to vertices in $V_1$.  So, let this $w$ be added to $V_1$ as the new $v$.
Specifically, $w$ is added to $V_1$, all the edges incident to $w$ are added to $E_0$, and all neighbors of $w$ not already in $V_2$ are added to $V_2$.  These operations maintain the three invariants:


*

*No edge of $E$ connects two vertices of $V_1$.

*Every edge of $E_0$ connects a vertex of $V_1$ to a vertex of $V_2$.

*Any two vertices in $V_1 \cup V_2$ are connected by a path with edges in $E_0$.


The process continues until the residual graph is empty, at which point $V_1 \cup V_2 = V$ and the desired property of the partition of vertices and subset of edges follows.  
As a side remark, if the residual graph is at any point complete, the process terminates in the next step.
