=== Problem R  Kruskal ===
  sorted edge list: B-C(1) D-E(2) A-B(3) F-G(3) C-D(4) A-C(5) B-D(6) E-F(7) D-F(8) C-E(9) E-G(10) G-H(11) F-H(12)
  step  edge   w  find(a) find(b)  verdict   disjoint-set forest
     1   B-C   1       B       C  ACCEPT    p:ABBDEFGH  r:01000000
     2   D-E   2       D       E  ACCEPT    p:ABBDDFGH  r:01010000
     3   A-B   3       A       B  ACCEPT    p:BBBDDFGH  r:01010000
     4   F-G   3       F       G  ACCEPT    p:BBBDDFFH  r:01010100
     5   C-D   4       B       D  ACCEPT    p:BBBBDFFH  r:02010100
     6   A-C   5       B       B  reject    p:BBBBDFFH  r:02010100
     7   B-D   6       B       B  reject    p:BBBBDFFH  r:02010100
     8   E-F   7       B       F  ACCEPT    p:BBBBBBFH  r:02010100
     9   D-F   8       B       B  reject    p:BBBBBBFH  r:02010100
    10   C-E   9       B       B  reject    p:BBBBBBFH  r:02010100
    11   E-G  10       B       B  reject    p:BBBBBBBH  r:02010100
    12   G-H  11       B       H  ACCEPT    p:BBBBBBBB  r:02010100
  |V|-1 = 7 edges taken; the remaining 1 edges cannot be needed
  MST: B-C(1) D-E(2) A-B(3) F-G(3) C-D(4) E-F(7) G-H(11)
  total weight 31

=== Problem S  Prim from A ===
  step  extract  edge committed  running total  queue (v:key/pi)
     1        A          (root)              0  B:3/A C:5/A D:inf E:inf F:inf G:inf H:inf 
     2        B          A-B(3)              3  C:1/B D:6/B E:inf F:inf G:inf H:inf 
     3        C          B-C(1)              4  D:4/C E:9/C F:inf G:inf H:inf 
     4        D          C-D(4)              8  E:2/D F:8/D G:inf H:inf 
     5        E          D-E(2)             10  F:7/E G:10/E H:inf 
     6        F          E-F(7)             17  G:3/F H:12/F 
     7        G          F-G(3)             20  H:11/G 
     8        H         G-H(11)             31  (empty)
  Prim's tree: A-B B-C C-D D-E E-F F-G G-H
  total weight 31  -- the same as Kruskal's

=== Problem U  the cut property and the cycle property ===
  cut S = {A,B,C}, V-S = {D,E,F,G,H}
  crossing edges: B-D(6) C-D(4) C-E(9)
  the light edge is C-D of weight 4
  is it in the MST found in Problem R? yes  -- exactly as Theorem 11.5 promises
  the cycle property, checked on every non-tree edge:
    A-C(5): closes the cycle C-B-A, whose heaviest tree edge weighs 3  -> strictly heaviest, so in NO MST
    B-D(6): closes the cycle D-C-B, whose heaviest tree edge weighs 4  -> strictly heaviest, so in NO MST
    C-E(9): closes the cycle E-D-C, whose heaviest tree edge weighs 4  -> strictly heaviest, so in NO MST
    D-F(8): closes the cycle F-E-D, whose heaviest tree edge weighs 7  -> strictly heaviest, so in NO MST
    E-G(10): closes the cycle G-F-E, whose heaviest tree edge weighs 7  -> strictly heaviest, so in NO MST
    F-H(12): closes the cycle H-G-F, whose heaviest tree edge weighs 11  -> strictly heaviest, so in NO MST

=== Problem V  union by rank and path compression ===
  operation   result   forest
  Union(A,B)   merged   p:AACDEFGH  r:10000000
  Union(C,D)   merged   p:AACCEFGH  r:10100000
  Union(E,F)   merged   p:AACCEEGH  r:10101000
  Union(G,H)   merged   p:AACCEEGG  r:10101010
  Union(A,C)   merged   p:AAACEEGG  r:20101010
  Union(E,G)   merged   p:AAACEEEG  r:20102010
  Union(A,E)   merged   p:AAACAEEG  r:30102010
  Find on every element, to show path compression:
    A->A B->A C->A D->A E->A F->A G->A H->A 
    p:AAAAAAAA  r:30102010
  the tallest possible tree on 8 elements with union by rank has height 3 = lg 8; without it, a chain of 8 would have height 7

=== Problem W  is the minimum spanning tree unique? ===
  the MST weighs 31
    delete B-C(1): best spanning tree now weighs 35   heavier
    delete D-E(2): best spanning tree now weighs 37   heavier
    delete A-B(3): best spanning tree now weighs 33   heavier
    delete F-G(3): best spanning tree now weighs 38   heavier
    delete C-D(4): best spanning tree now weighs 33   heavier
    delete E-F(7): best spanning tree now weighs 32   heavier
    delete G-H(11): best spanning tree now weighs 32   heavier
  rows with the same weight: 0  -> the MST is UNIQUE
  note: the weights are NOT all distinct (A-B and F-G both weigh 3),
  and yet the tree is unique. Distinct weights are sufficient, not necessary.
  now lower A-C from 5 to 3: the MST weighs 31; deleting each tree edge:
    dropping A-B still gives 31 -- a second MST
  alternatives found: 1
