I came across following problem:
The solution given was as follows:
There are two ways to reach node $F$, one from node $A$, other from node $G$. Maximum weight of the edge in MST is smallest of two. Hence 11. Similarly there are four edges incident on node $B$, having weights $13,14,8,z$. If $z$ is included in MST, then it should be at least $min(13,14,8)$, that is 8.
Then I came across another problem:
In every cycle, the weight of an edge that is not part of MST must by greater than or equal to weights of other edges which are part of MST. Since all edge weights are distinct, the weight must be greater. So $w(ED)=6, w(CD)=15$ and $w(AB)=9$
First solution chooses min degree of a node, whereas second solution chooses max edge weight in cycle. This seems to be obvious since first problem has "unknown MST edge weights", whereas second problem have "unknown non-MST edge weights".
But, I have several doubts here:
In solution 1, why we examine edges incident on node $B$ only, but not node $C$? I guessed following procedure:
If we start preparing MST using Kruskal's algorithm, we will go on adding edges in sequence $AG,IJ,CD,...$ and $C$ gets connected to MST. So in this particular example, it works by preparing MST using the known edge weights such that the edges chosen wont change whatever the unknown weights turn out to be. And then based upon vertices connected to the MST prepared so far, decide which of the vertices of unknown weight edge is to be reached by that edge.
Is this procedure correct? Does it work in all cases / graphs? Is there any other standard approach to solve such problem?
Second solution used cycle $E-D-F-E$ to determine the weight of edge $ED$, but not cycle $B-E-D-C$. Though I understand that decision of choosing $EF$ and $DF$ are dependent on $ED$, doesnt decision of selecting $BE$ is dependent on total of weights of $CD$ and $ED$? What is exact rule/idea for deciding which cycle to consider while determining non MST edge weight?
Is there some standard well defined steps for both problems? Or its more sort of trial and error work?