Whats wrong with my counterexample for an MST CUT?

58 Views Asked by At

bevor I start, I want to mention, that there is an quivalent problem here How to I have to understand the Cut in an graph in this case?

But the answer doesn't help me so.

Following Problem: Given is an Graph $G=(V,E)$, a minimal spanning Tree $G'=(V,E')$ with $k : E \rightarrow \mathbb{R}$.

Let $f = \{x, y\} \in E'$ and let $A$ be the set of all nodes reachable from $x$ in $(V, E' \setminus {f})$. Then for every edge $e \in \delta(A)$ ($\delta(A) := \{ e = \{v, w\} \in E \mid v \in A \text{ and } w \in V \setminus A \}$) it holds that $c(e) \geq c(f)$.

Now i tired to understand this definition, but if I draw it, I get this drawed counterexample

What I am I doing wrong

1

There are 1 best solutions below

0
On BEST ANSWER

In your example you write $A = \{6,7\}$, but this is incorrect: the set of all nodes reachable from $x$ includes (trivially) $x$. So in your case $A = \{4,6,7\}$, and then $\delta(A)$ indeed only contains edges with weight at least that of $f$.