Let $G = (V, E)$ be a graph, $w: E \rightarrow \mathbb{R}^+$ a weight function, $T=(V, E_T)$ a minimum spanning tree of $G$.
I have to show that for all edges $\{u,v\} \in E_T$ there exists a cut such that $\{u, v\}$ is light.
I think it's intuitively correct, since otherwise there wouldn't be such a minimum spanning tree, so I tried a proof by contradiction that goes like this:
Assume there exists an edge $e\in E_T$, such that for all cuts including $e$ there exists an edge $e'$ in this cut with $w(e) > w(e')$.
$\Rightarrow$ $\exists (T\backslash\{e\}) \cup\{e'\}$ whose total weight is smaller than $T$, therefore $T$ cannot be a minimum spanning tree.
Is this proof correct or am I missing some crucial parts here? I'm a computer science student who is new to graph theory
Best Answer
You line of reasoning does not suffice yet. It is not clear that $[T \setminus \{e\}] +\{e'\}$ as you specified is connected, and this is the crux of what you would need to show to count as a proof: You need to show existence of a cut $C \subset E(G)$ containing $e$ that guarantees that the resulting $[T \setminus \{e\}] +\{e'\}$ is indeed connected, with $e,e' \in C$ and $w(e') < w(e)$, if there is such an edge $e'$. And you didn't do that here yet.
This is how I would do it: $T \setminus \{e\}$ has precisely 2 connected components [why is that] and let $V_1$ be the set of vertices in one such connected component, and $V_2$ be the set of vertices in the other. Then let $C$ be the cut in $G$ between $V_1$ and $V_2$ i.e., $C$ is precisely the set of edges in $G$ with one endpoint in $V_1$ and the other in $V_2$. Then $e \in C$, and for every edge $e'' \in C$, the resulting $[T \setminus \{e\}] +\{e''\}$ is indeed connected. Make sure you see why.
Can you finish from here.