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

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:

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?

Solution was:

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:

1. 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?

2. 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?

3. Is there some standard well defined steps for both problems? Or its 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.