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 Answer 1

Reset to default
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$
4
  • $\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, 2017 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, 2017 at 20:21
  • $\begingroup$ Do you add the edge connecting $w$ to some vertex in $V_2$ to $E_0$? $\endgroup$
    – pi66
    Feb 21, 2017 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, 2017 at 20:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .