Question

某工厂生产由6种不同颜色的纱织成的双色布.已知在品种中,每种颜色至少分别和其他5种颜色中的3种颜色搭配,证明可以挑出3种

Answer 1

令每个结点表示一种颜色,每条边表示存在一个双色布品种,该品种由端点代表的两个颜色搭配.

该问题转化成：

已知：某个n(G)=6的图G,其每个点的度至少是3,

证明：该图存在一个完美匹配.

证明过程：

下面证明一个更强更一般化的结论,

定理：如果n(G)≥3,且结点的最小度不小于n(G)的一半,则G是哈密顿图.

关于该定理的证明,请参考《图论导引》（第二版,机械工业出版社）的定理7.2.8