問題

重み付き連結無向グラフと枝集合の部分集合の族がある。
ここではマトロイドをなしているとする。
さらに独立集合と枝を任意にとったとき、が上で連結でないならばが常に成り立つとする。
このときマトロイドの最小重み基はの最小全域木を含むことを華麗に示せ。

クラスカル法とマトロイドの貪欲アルゴリズムをなぞってみれば自明だけどなんか証明が美しくないのでマトロイドの構造を利用して示せないだろうか。