3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ I think you're counterexample is right, so the theorem can't be true. Isn't there some other condition on $A$ and $B$? $\endgroup$
    – Ragnar
    Feb 6, 2014 at 14:32
  • $\begingroup$ It just says that $A,B$ are cuts, nothing more, and that $G$ is an undirected graph (which doesn't do any difference). $\endgroup$ Feb 6, 2014 at 14:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ragnar
    Feb 6, 2014 at 14:39

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.