完全图移除n-1条边后无完美匹配时边集是否必为星型的问题

问题描述 #

假设 $n \ge 6$ 且为偶数，考虑完全图 $K_n$，移除其中 $n-1$ 条边构成集合 $S$（剩余的图记为 $G = K_n - S$）。现在有个疑问：如果 $G$ 中不存在完美匹配，那么 $S$ 是否一定是一个星型边集——也就是所有被移除的边都共享同一个顶点？

我的尝试思路 #

我目前在尝试用Tutte定理来推导证明，但总觉得现有约束条件还不够充分。具体步骤如下：

• 设 $U$ 是顶点集的一个子集，记 $G[V \setminus U]$ 的奇分支数量为 $t$。根据Tutte定理，若 $G$ 不存在完美匹配，则必然存在这样的 $U$ 满足 $t > |U|$。
• 基于这个前提，我推导出了两个不等式：
  1. $\binom{t}{2} \le n-1$
  2. $t+1 \le n$（这里假设 $U \neq \emptyset$）

但目前这两个不等式似乎还不足以推出 $S$ 必须是星型结构，暂时陷入了瓶颈。

备注：内容来源于stack exchange，提问作者Connor