Proof of optimal substructure Proof. Cut and paste ()=(l23y)+w(71)+w(72) If Ti were a lower-weight spanning tree than T, for 1, then T'=l(u,DUTUT2 would be a lower-weight spanning tree than T for G. L Do we also have overlapping subproblems? Y es Great then dynamic programming may work Yes, but MsT exhibits another powerful property which leads to an even more efficient algorithm c 2001 by Charles E Leiserson Introduction to Agorithms Day 27 L16.8© 2001 by Charles E. Leiserson Introduction to Algorithms Day 27 L16.8 Proof of optimal substructure w(T) = w(u, v) + w(T1) + w(T2). Proof. Cut and paste: If T1′ were a lower-weight spanning tree than T1 for G1, then T′ = {(u, v)} ∪ T1′ ∪ T2 would be a lower-weight spanning tree than T for G. Do we also have overlapping subproblems? •Yes. Great, then dynamic programming may work! •Yes, but MST exhibits another powerful property which leads to an even more efficient algorithm