1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do you know the residual graph is still connected? Maybe some two vertices need to go through $v$ to reach each other? $\endgroup$ – pi66 Feb 21 '17 at 20:16
  • $\begingroup$ I misspoke. What I wanted to say is that the residual graph is not disconnected from the nodes in $V_2$. You don't need the stronger property, which is not true, as you point out. I fixed my post. $\endgroup$ – Fabio Somenzi Feb 21 '17 at 20:21
  • $\begingroup$ Do you add the edge connecting $w$ to some vertex in $V_2$ to $E_0$? $\endgroup$ – pi66 Feb 21 '17 at 20:45
  • $\begingroup$ Yes, $w$ is added to $V_1$, all the edges incident on $w$ are added to $E_0$, and all neighbors of $w$ not already in $V_2$ are added to $V_2$. The three invariants in your post are all maintained by these operations. I'll add the details. $\endgroup$ – Fabio Somenzi Feb 21 '17 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.