2021 年吉林预赛

解答

构造一个图 $G$：十个点作为顶点，两个点不构成“同标点对”时就在它们之间连边。 题目所求的分组正是 $G$ 的一个完美匹配。

先令 $m=4$。每个顶点至多有 $4$ 个“同标”伙伴，所以在其余 $9$ 个顶点中， 至少与 $5$ 个相连，即

取 $G$ 的一个最大匹配。若它不是完美匹配，则至少有两个未匹配顶点 $u,v$， 而匹配边数至多为 $4$。由最大性，$u,v$ 不相邻，且它们的所有邻点都已经被匹配。

对任意一条匹配边 $xy$，从 $u,v$ 到 $\{x,y\}$ 的边总数至多为 $2$。 否则至少存在两条端点互异的边，分别把 $u,v$ 接到 $x,y$， 便可删去匹配边 $xy$ 并加入这两条边，使匹配边数增加，产生矛盾。 因此

但最小度数条件又给出

矛盾。故 $G$ 必有完美匹配，$m=4$ 可行。

下面说明 $m=5$ 不可行。取六个点

再取四个点

前六点中的每一点恰与其余五点构成“同标点对”，后四点不与任何其他点同标， 故每点的同标伙伴数均不超过 $5$。然而前六点彼此不能配成允许的点对， 它们必须分别与后四点配对，而后四点只有四个，不可能全部配完。 所以 $m=5$ 已不能保证题设结论。

因此 $m$ 的最大值为 $\boxed{4}$。