无6及以下环的无向图中，第四轻边必在所有MST中吗？

问题描述 #

给定无向图 ( G=(V,E) )，权重函数 ( w:E \to \mathbb{R} )，满足以下条件：

• 所有边的权重互不相同；
• ( G ) 中不存在长度为6或更短的环。

设 ( e_4 ) 为图中第四轻的边（恰好有3条边的权重比它小），求证或证伪：( G ) 的每棵最小生成树（MST）都必然包含 ( e_4 )。

我的尝试 #

采用反证法推导：假设存在一棵不含 ( e_4 ) 的MST ( T )，记 ( e_1、e_2、e_3 ) 为三条权重轻于 ( e_4 ) 的边。将 ( e_4 ) 加入 ( T ) 会形成唯一的环，若用 ( e_1、e_2、e_3 ) 中的边替换环内某条权重更大的边，得到新生成树 ( T' )，但 ( T' ) 会形成长度为4的环，这与题目中“G不含长度6或更短的环”的条件矛盾。因此原假设不成立，可推出 ( G ) 的每棵MST都包含 ( e_4 )。

内容的提问来源于stack exchange，提问作者ATB