title: Find minimum-weight complete graph that spans a given minimum spanning tree
body: <p>Let <em>T = (V, E)</em> be a tree of <code>|V|</code> vertices and <code>|E| = |V-1|</code> edges, with known costs. We want to construct a minimum-weight <strong>complete</strong> Graph <em>G = (V, E')</em> that spans <em>T</em> as its unique minimum spanning tree.</p>
  
  <p>Example: consider the following tree <em>T</em>. Edges in <strong>red</strong> have a given cost. Dotted edges will be added to construct a complete graph from this tree.</p>
  
  <p><img src="https://i.stack.imgur.com/EvBIZ.png" alt="Tree"></p>
  
  <p>The minimum-weight complete graph <em>G</em> that spans <em>T</em> as its unique MST is the following:</p>
  
  <p><img src="https://i.stack.imgur.com/43ys3.png" alt="Complete Graph"></p>
  
  <hr>
  
  <p>I am trying to find a (polynomial-time) algorithm that generates this graph. I am looking mostly for a tip, not the complete solution. So far, I have devised the following algorithm:</p>
  
  <p>1) Find a cut of the graph that includes the heaviest MST edge of weight <code>w_max</code> and no other MST edges. All other edges have to be <code>w_max + 1</code>. The following pictures illustrates my idea:</p>
  
  <p><img src="https://i.stack.imgur.com/OYw6W.png" alt="Cut on the heaviest MST edge"></p>
  
  <p>Edges (1--2), (1--4), (4--5), (2--3) and (2--5) are included in this cut <em>C</em>. The only edge that is included in the MST is edge (2--3) and it's the heaviest edge in the MST, with <code>w=56</code>. Thus, all other edges should have <code>w=57</code>. Proof: assume the contrary; we can replace (2--3) with another edge and still keep the tree connected. Now the tree's weight is lighter, thus (2--3) doesn't belong to the MST. Contradiction.</p>
  
  <p>2) Repeat for all other edges <code>e_i</code> of the MST, of weight <code>w_i</code>, in decreasing weight order. Take a cut that includes only <code>e_i</code> and no other MST edges. Any unknown non-MST edge of this cut, should have a weight of <code>w_i + 1</code>.</p>
  
  <hr>
  
  <p>Questions:</p>
  
  <p>1) Is the above algorithm correct? According to the Cut property, it should be.</p>
  
  <p>2) Could I do it more efficiently? I don't have an algorithm to find cuts on the top of my head, but I don't feel this approach could be efficient.</p>
  
  <hr>
  
  <p><em>edit</em>: Another approach that I had in my mind was an approach based on Kruskal's algorithm:</p>
  
  <p>1) Using a Union-Find, I iterate all MST edges, by ascending cost, and unify the corresponding vertices under the same component.</p>
  
  <p>2) In each step, two different components are unified through an edge of cost <code>w</code>. Any other edges that form a cycle within the same (new) component should have a cost of <code>w+1</code>.</p>