Finding missing edge weights in the context of minimum spanning tree

Question

I came across following problem:

Problem 1
Suppose that minimum spanning tree of the following edge weighted graph contains the edges with weights $x$ and $z$, then what are $x$ and $z$? enter image description here

The graph was given as follows:

Let vertices $A, B, C, D, E$ be drawn in the first line and vertices $F, G, H, I, J$ be drawn in the second line. The weights in the first line are $w(AB) = 13$, $w(BC) = z$, $w(CD) = 2$, $w(DE) = 6$, in the second line are $w(FG) = x$, $w(GH) = 4$, $w(HI) = 3$, $w(IJ) = 1$, and the rest are $w(AF) = 11$, $w(AG) = 1$, $w(BG) = 14$, $w(BH) = 8$, $w(CH) = 12$, $w(DH) = 9$, $w(DI) = 6$, $w(DJ) = 7$, $w(EJ) = 5$.

The solution was given 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:

Problem 2
In below graph, the edge weights of only those edges which are in the MST are given. What are the weights of other edges?
enter image description here

The graph was given as follows:

Let vertices $A, B, C$ form a triangle on the left, vertices $B, C, D, E$ form a square on the middle, vertices $D, E, F$ form a triangle on the right. The weights are $w(AB) = x$, $w(AC) = 9$, $w(BC) = 2$, $w(BE) = 15$, $w(CD) = y$, $w(DE) = z$, $w(DF) = 6$, $w(EF) = 4$.

The solution was given as follows:

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$.

The first solution chooses min degree of a node, whereas the second solution chooses max edge weight in cycle. This seems to be obvious since the first problem has "unknown MST edge weights", whereas the second problem have "unknown non-MST edge weights".

But, I have several doubts here:

1. In the first solution, why do we examine edges incident on node $B$ only, but not node $C$? I guessed the following procedure:

If we start preparing MST using Kruskal's algorithm, we will go on adding edges in sequence $AG, IJ, CD, \cdots$ 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 won't 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 or graphs? Is there any other standard approach to solve such problem?

2. In the second solution, we use 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$, doesn't 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?

3. Are there some standard well-defined steps for both problems? Or is it more sort of trial-and-error work?

Answer 1

Firstly, to make the nice answer given by OP to Problem 1 the only valid answer, we should change its question "what are $x$ and $z$?" to "what are the maximal weights of $x$ and $z$?". Otherwise, we can have many valid answers such as "$x=3, z = 5".

Secondly, to make the nice answer given by OP to Problem 2 the only valid answer, we should change its question "What are the weights of other edges?" to "What are the minimal weights of other edges?". Otherwise, we can have many valid answers such as "$w(ED)=16, w(CD)=115$ and $w(AB)=19$".

Lastly and most importantly, let us answer the central question, "Is there some standard well defined steps for both problems? Or its more sort of trial and error work?". A standard way to rephrase the question is, "Is there an effective algorithm for both kinds of problems?"

Let $G$ be an edge-weighted connected undirected graph with some unknown weights. Let us state the questions clearly in more detail. We will assume there are graphs that satisfy the given conditions in the problems. (Otherwise, we can add extra steps to the algorithms below to detect those impossible situations).

The first kind of problem: unknown weights in an MST

Assume that we know a minimum spanning tree (MST) of $G$ such that all edges of unknown weights belong to that MST. What are the maximal values of those unknown weights?

Here is the sketch of an effective algorithm, which can be considered as a precise abstraction of OP's concrete solving procedure.

Pick any edge $e$ that is not that MST. If we add $e$ to that MST, we will create a unique simple cycle. All edges of MST in this cycle must be as light as or lighter than $e$. Collect these inequalities, all of which have the form "$x\leq a$" where $x$ is the unknown weight of some edge in that MST and $a$ is a known number. Repeat until we have gone through all edges that are not in that MST.

Now we have a collection of inequalities about some unknowns and numbers. Remove redundant inequalities. Find an inequality "$x\leq a$" with the smallest number $a$ where $x$ is an unknown. Let $x=a$ be part of the answer. Repeat this process until we have no more inequalities.

The second kind of problem: unknown weights outside an MST

Assume that we know a minimum spanning tree (MST) of $G$ such that all weights of edges of the MST are known. What are the minimal values of the unknown weights?

Here is the sketch of an effective algorithm, which can be considered as a precise abstraction of OP's concrete solving procedure.

Pick any edge $e$ of unknown weight. If we add $e$ to that MST, we will create a unique simple cycle. All edges of MST in this cycle must be as light as or lighter than $e$. Collect these inequalities, all of which have the form "$a\leq x$" where $x$ is the unknown weight of $e$ and $a$ is a known number. Repeat until we have gone through all such edge $e$ of unknown weight.

Now we have a collection of inequalities about some unknowns and numbers. Remove redundant inequalities. Find an inequality "$a\leq x$" with the largest number $a$ where $x$ is an unknown. Let $x=a$ be part of the answer. Repeat this process until we have no more inequalities.

More general problems?

If you have read this far, it will be obvious that we could create more general problems of similar kinds. We will have a general approach towards producing an algorithm as well. So much for my answer that is already long.