Is Partitioning a Graph into Two Sets a Cut Set?

[Ackbach]

Here is this week's POTW:

-----

Show that if the vertex set of a connected graph $G=(V,E)$ is partitioned into two nonempty sets $X$ and $Y$, the disconnecting set $F=(X,Y)$ consisting of all edges of $G$ joining vertices in $X$ and vertices in $Y$ is a cut set if the subgraph $G'=(V,E-F)$ has exactly two components.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

No one answered this week's POTW, which is taken from the Schaum's Outlines Graph Theory book, by Balakrishnan. Here is the book's answer:

Spoiler

Suppose $F=(X,Y)$ is not a cut set. Then there is a proper subset $F'$ of $F$ that is a cut set. Let $e=\{x,y\}$ in an edge in $F-F'$ joining vertex $x$ in $X$ and vertex $y$ in $Y$. If $v$ is any vertex in $X$, there is a path joining $v$ and $x$ consisting of vertices from $X$ only. Likewise, if $w$ is any vertex in $Y$, there is a path joining $w$ and $y$ consisting of vertices from $Y$ only. Thus the deletion of all the edges belonging to $F'$ from the graph will not make it disconnected. This is a contradiction since $F'$ is a disconnecting set.