MHB Is Partitioning a Graph into Two Sets a Cut Set?

  • Thread starter Thread starter Ackbach
  • Start date Start date
  • Tags Tags
    2016
Ackbach
Gold Member
MHB
Messages
4,148
Reaction score
93
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!
 
Physics news on Phys.org
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:

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.
 
Back
Top