我的笔记告诉我，第一个和 最后一个假设M是加权图-GR的最小生成树 设A是GR的一个顶点，则M-{A}也是GR-{A}的MST。 设A是M的一个叶，则M-{A}也是GR-{A}的MST。 如果e是M的边，则(M-{e}(是M1和M2树的森林，使得对于M_i，i=1,2是顶点T_i上的诱导图GR的MST。
- 设A是GR的一个顶点，则M-{A}也是GR-{A}的MST
这是错误的。
如果A不是叶，则M-｛A｝不是连通图，因此它不可能是MST。
更详细地说：A至少有两个邻居，并且存在于其中两个邻居之间的单个路径(MST属性(包括A。如果A被移除，那么在这两个其他顶点之间就没有更多的路径了。
设A是M的一个叶，则M-{A}也是GR-{A}的MST
这是真的。
由于A是一个叶，M-{A}是一个连通图，并且比M少了一条边：它没有与M中的A相连的边e。
现在假设M-{A}不是GR-{A}的MST。我们知道M-{A}是一个连通图，并且没有循环——否则M就不是MST。因此，如果它不是MST，那么它的重量一定不会最小化。然后有一个不同的图P，是GR-{a}的MST。但P+e的总权重会小于M，但仍然是GR的生成树。所以M不可能是GR的MST。这是一个矛盾，所以最初的说法是正确的。
- 如果e是M的边，则M-｛e｝是M1和M2树的森林，使得对于Mi，i=1,2是顶点Ti上的诱导图GR的MST
这是真的。你在这张纸上的笔记错了。
让我们假设Mi(对于i=1,2(不是顶点Ti上的诱导图的MST。我们知道Mi不是断开的(移除e正好创建2个连通图(，并且它没有循环(否则M也会有这些循环(。因此，如果它不是MST，那么原因是它的权重没有最小化，而另一个图Pi是该诱导图上的MST，并且总权重小于Mi。
如果您随后重新引入边e，并将pi与M3-i连接，则GR的生成树的权重将小于M，因此M不是MST。这又是一个矛盾，所以最初的说法是正确的。