好吧问答库 > 请教图论问题。谢谢。

请教图论问题。谢谢。

http://zhidao.baidu.com/question/28707090.html用图论解答某工厂生产由6种不同颜色的纱织成的双色布。已知在品种中，每种颜色至少分别和其他5种颜色中的3种颜色搭配，证明可以挑出3种双色布，它们恰有6种不同的颜色。可以答得更详细些吗？“由于要恰好6种颜色的布料所以要除以重复的次数也就是5种布料任选2种＝10种60/10＝6”引号里不明白，有没有相关的例题。感谢。

2026年09月24日 16:17

有2个网友回答

网友（1）：

令每个结点表示一种颜色，每条边表示存在一个双色布品种，该品种由端点代表的两个颜色搭配。
该问题转化成：
已知：某个n(G)=6的图G，其每个点的度至少是3,
证明：该图存在一个完美匹配。
证明过程：
下面证明一个更强更一般化的结论，
定理：如果n(G)≥3，且结点的最小度不小于n(G)的一半，则G是哈密顿图。
关于该定理的证明，请参考《图论导引》（第二版，机械工业出版社）的定理7.2.8

网友（2）：

为了保持唯一性，要排除蓝-红，红-蓝，为两种情况的可能性，所以要除以重复次数