我与几个合作伙伴研究这个图论问题已有一段时间了。我们被卡住了，很想给我们一个正确的方向。
这里是问题：
图G的顶点集为{1,2 ... 60}，并且如果x！= y并且x * y被6整除，则两个顶点x，y通过边连接。确定最大数v（ G）中的独立边。
所以我们知道6，12，18 ... 60都连接到每个顶点。我很难过。不寻找答案，请提示！谢谢。
考虑这种情况的一种方法是：每个边都需要链接两个数字，以便在两个端点之间有一个2除数和3除数。
在1到60之间（包括1和60之间的数字）中，有20个数字没有2或3的除数（即1、7、13、19，...和5、11、17 ...）。有10个数字，其中2和3除数（6，12，18，...）。有10个数字只有3个因数（3、9、21，...），有20个数字只有2个因数（2、8、14，...和4、10、16 ...）。
[至少有一个最优解，总是将具有2和3除数的数与没有2除数或3除数的数配对。 （您可以通过矛盾证明这一点）。所以从那开始。留下
那些没有2或3除数的10个数字与其他任何数字都不具有边，因此我们可以忽略它们。在其余数字中，从具有3个除数的所有数字到具有2个除数的所有数字都有一条边，因此您可以将所有10个数字与一个3除数配对，而将10个数字与仅2个除数配对。
总体上，您总共获得20条边：6的所有倍数，包含10个1或5 mod 6的数字，以及所有3 mod 6的10个2或4 mod 6的数字。
希望这会有所帮助！