IBM Ponder This #046 · 2002 年 2 月

Alan Hoffman 提出了这个问题。无向简单图 G 不含三角形或四边形，直径为 2，且各顶点的度不全相同。其中某个顶点的度为 7。G 一共有多少个顶点？请证明。

这里的边连接两个不同顶点，每对顶点之间至多一条边；禁止三角形和四边形，是指禁止长度为 3 和 4 的圈。直径为 2，意味着任意两个顶点之间都有长度不超过 2 的路径，而且至少有一对顶点的最短路径长恰好为 2。顶点的度是与它关联的边数。

官方背景说明：若改成所有顶点的度都等于 d，则已知候选只有五边形（d=2）、Petersen 图（d=3）、Hoffman–Singleton 图（d=7），以及一个可能存在、具有 3250 个顶点的 d=57 图；最后一种的存在性在原题中列为未知。

解答

认真尝试后再打开

待补充。