[Math] Show that a symmetric difference of edge cuts is an edge cut.

graph theory

I have two edge cuts $A,B$. An edge cut is a set of edges, whose removal from $G$ makes the graph disconnected (there exist some vertices $x,y$ such that there's no path connecting them). I need to prove, that the symmetric difference of those two sets is too an edge cut. Let $Z=(A \cup B)/(A \cap B)$

So there are a couple of cases to consider.

  1. $|A \cap B|=0$, then obviously the symmetric difference is an edge cut.

  2. $G-Z$ is disconnected, so it is an edge cut.

  3. $G-Z$ is for some reason connected. That would mean, that for every $x,y$ there exists a path between those two vertices, an it goes through some edges in $A \cap B$. An there probably lies a contradiction here somewhere, but where exactly I do not know…

This exercise is from one of the old exams I'm doing in preparations for my exam next week. Is there any possibility, that the exercise is just wrong? I mean take a look at this drawing.enter image description here

$1$ shows edge cut $A$, that separates the middle left vertex, $2$ shows edge cut $b$ that separates two bottom vertices from the left, and $3$ is their symmetrical difference that hardly does anything.

Best Answer

I found the problem: An edge cut isn't simply a set of edges whose removal makes the graph disconnected. An edge cut is the following:
Take a subset $A\subset V(G)$ of the vertices of $G$. Then, the edge cut $\delta(A)$ is the following: $$ \delta(A)=\{uv\in E(G)|u\in A,\, v\not\in A\} $$ In your first example, the middle-left vertex is the set $A$. The second example isn't an edge cut, because the point in the upper left is still connected to the point in the middle-left place, which wouldn't be possible if it was an edge cut. I found the explanation and the answer at problem $6$ here.

Related Question