TADM2E 6.17
From Algorithm Wiki
a) No, Look at the graph on page 196 for a counter example.
No to both. A counterexample to both is a four node, four edge graph connected in a square:
- Edge 1 - A:B, weight 1
- Edge 2 - B:C, weight 7
- Edge 3 - C:D, weight 2
- Edge 4 - D:A, weight 8
The MST is A:B:C:D, and edge 4 is never included. The path from A to D through the MST is 10, but the direct path through edge 4 is weight 8.
