Randomized MST example

The following picture shows a graph with 8 nodes and 15 edges. Assume this is the \(G'\) that results after 3 Boruvka steps at the beginning of the randomized MST algorithm.

MST example graph

Some of the edges in \(G'\) as drawn above are in bold blue. Assume those are the edges chosen randomly to be in \(H\).

Show the steps of the randomized MST algorithm for this graph \(G'\). I want to see:

• The subgraph \(H\) (by itself)
• The resulting MST \(F\) of \(H\) from the first recursive call
• Which edges in \(G'\) are \(F\)-light, and which are not.
• The graph \(G''\) that will be sent to the second recursive call.
• The result of the second recursive call, which will be the MST of \(G'\).

I know some of the labels in the graph above are hard to read. To help with that, keep in mind that all the labels are drawn in the middle of the edge length-wise, and off to one side. Here is a text listing of all the edges that should clarify any discrepancy:

  C -- E [label="1"];
  C -- D [label="2"];
  A -- B [color=blue,penwidth=2,label="3"];
  D -- E [color=blue,penwidth=2,label="4"];
  A -- F [label="5"];
  G -- H [color=blue,penwidth=2,label="6"];
  C -- G [color=blue,penwidth=2,label="7"];
  D -- H [color=blue,penwidth=2,label="8"];
  D -- G [label="9"];
  E -- H [color=blue,penwidth=2,label="10"];
  C -- H [color=blue,penwidth=2,label="11"];
  A -- D [color=blue,penwidth=2,label="12"];
  B -- H [color=blue,penwidth=2,label="13"];
  F -- G [color=blue,penwidth=2,label="14"];
  A -- H [label="15"];