# Show that a symmetric difference of edge cuts is an edge cut.

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.

$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.

• I think you're counterexample is right, so the theorem can't be true. Isn't there some other condition on $A$ and $B$? Feb 6, 2014 at 14:32
• It just says that $A,B$ are cuts, nothing more, and that $G$ is an undirected graph (which doesn't do any difference). Feb 6, 2014 at 14:33
• In that case I think the exercise is wrong, although it is from an exam, so maybe there is something I'm missing. Found the problem, see my answer. Feb 6, 2014 at 14:39

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.