我遇到了一个问题，我试图自己解决，但我没有找到足够令人满意的答案。
问题：
给定一个无向图 G = (V, E) ，权重函数为 w: E->R 这样 假设 G 不存在两条具有相同权重的边 不包含 6 或更短的循环长度。
令 e4 为权重中的第四条边，因此恰好有 3 边缘的权重比 e4 轻。
证明或反驳：G的每个MST都包含e4。
我的尝试：
为了矛盾起见，假设存在 G 的 MST，不包含边 e4。
设 T 为 G 的不包含 e4 的 MST。
鉴于正好有 3 条边的权重小于 e4 的权重，将这些边按权重非递减顺序表示为 e1、e2 和 e3。
考虑从 T 中删除 e4。由于 T 是一棵树，删除 e4 会将 T 断开为两棵子树，表示为 T1 和 T2，其中 e4 最初连接 T1 和 T2 中的顶点。
由于 T 是 MST，因此它必须具有 G 的所有生成树中的最小总权重。因此，删除 e4 并用边 e1、e2 和 e3（比 e4 轻）替换它，必然会生成具有以下性质的生成树：总重量小于 T。
设 T' 为将 T 中的 e4 替换为边 e1、e2、e3 得到的生成树。
但是，T' 与 e1、e2、e3 和 T 中的现有边形成长度为 4 的循环。这与 G 中不存在长度为 6 或更小的循环的给定条件相矛盾。
因此，我们假设 G 存在不包含 e4 的 MST 是错误的。
因此，对于 G 的每个 MST，该 MST 都包含边 e4。
Kruskal 算法通过贪婪地选择不会导致循环的最低权重边来构造 MST。由于没有循环长度为 5 或更小，因此必须选择 e4。