Sabatier conjectures

ignougroup
Problem Detail: While I was doing CLRS (3rd edition), I came across this question on page 629: Professor Sabatier conjectures the following converse of Theorem 23.1:

Let $G = (V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A subseteq E$ that is included in some minimum spanning tree for $G$, let $(S,V -S)$ be any cut of $G$ that respects $A$, and let $(u,v)$ be a safe edge for $A$ crossing $(S, V – S)$. Then, $(u,v)$ is a light edge for the cut.

Show that the professor’s conjecture is incorrect by giving a counterexample. Theorem 23.1:

Let $G = (V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, let $(S, V – S)$ be any cut of $G$ that respects $A$, and let $(u,v)$ be a light edge crossing $(S, V – S)$. Then, edge $(u,v)$ is safe for $A$.

Can anybody please give a proof or a counterexample to the conjecture also because I used to think that all safe edges added to the graph are light edges.

DEFINITIONS :
1. Cut (S ,V-S) : of an undirected graph G = (V,E) is a partition of V(as defined in CLRS Book) .You can think it as a line that divides graph into two disjoint sets of vertices on its either side.
2. Light edge:Any edge crossing a cut is light edge if its weight is the minimum of all the edge crossing the cut.Light edge is defined with respect to a particular Cut.
3. A cut Respects a set A of edges if no edge in A crosses the cut.
4. Safe edge is the edge which we can add to MST without any violation of MST’s property.These are those edges which are the part of final MST.

I have written most of the definition but for more queries you can also refer to CLRS chapter 23.

Asked By : RYO

Answered By : D.W.

OK, here’s a big hint. Take any $G,A,S$ that satisfy the premises of the question. Now add a new vertex $v’$ to the graph, and draw an edge from $v’$ to one of the vertices of $A$ with a weight of your choice. (This means that $v’$ will be connected to the rest of the graph only by this one new edge; there are no other edges out of $v’$.) What can you say about this new edge? Does it cross the cut? Is it a light edge? Is it a safe edge? Does this suggest any method for choosing the weight on that edge, to make things fortuitous to you? Hint: if you think about it (or try some examples), I bet you’ll see how you can arrange things to get a violation of the conjecture. People learn best by finding the solution for themselves (rather than reading someone else’s solution), so I’m not going to post more than a hint. This hint ought to be enough to understand what’s going on here….
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13008