各位图论圈的同行们，今天带来一个有意思的教授悬赏问题：有位教授给学生们开出奖励，只要能找到一个包含30个顶点的图 $G=(V,E)$，满足下面一系列严苛的约束条件就行。先统一符号：我们记 $n_{u,v}$ 为顶点 $u$ 和 $v$ 的公共邻居数量。

核心约束条件 #

首先是图本身的局部性质：

• 局部线性条件：对于任意边 ${u,v} \in E$，都有 $n_{u,v}=1$。也就是说，图里任意两个相邻顶点恰好有1个共同邻居。

接下来是三个着色相关的约束，我们需要存在两个正常着色 $f:V\rightarrow [3]$（3着色）、$g:V\rightarrow [5]$（5着色），以及一个不一定正常的着色 $h:V\rightarrow[2]$（2着色），满足以下条件：

• 跨3着色两颜色的诱导子图性质：对于所有不同的 $x,y\in[3]$，由 $f^{-1}(x) \cup f^{-1}(y)$ 诱导的子图是2-正则图（每个连通分支都是环）。
• 同3着色顶点的公共邻居限制：对于任意两个不同的顶点 $u,v\in V$，如果 $f(u)=f(v)$（同属3着色的同一个颜色类），那么它们的公共邻居数量 $n_{u,v}\leq1$。
• 3着色与5着色的交叉计数约束：对于任意 $x\in[3]$ 和 $y\in[5]$，$|f^{-1}(x)\cap g^{-1}(y)|=2$。简单说就是每个3着色的颜色类和每个5着色的颜色类的交集恰好有2个顶点（3×5×2=30，刚好对应总顶点数）。
• 同3着色+5着色顶点的公共邻居条件：对于任意两个不同的顶点 $u,v\in V$，如果 $f(u)=f(v)$ 且 $g(u)=g(v)$，那么它们的公共邻居数量 $n_{u,v}=0$。
• 三着色交叉计数约束：对于任意 $x\in[3]$、$y\in[5]$ 和 $z\in[2]$，$|f^{-1}(x)\cap g^{-1}(y)\cap h^{-1}(z)|=1$。也就是说，每个3着色、5着色、2着色的颜色类交集恰好有1个顶点（3×5×2=30，同样匹配总顶点数）。
• 异3着色但同5+2着色顶点的公共邻居条件：对于任意两个不同的顶点 $u,v\in V$，如果 $f(u)\neq f(v)$ 但 $g(u)=g(v)$ 且 $h(u)=h(v)$，那么它们的公共邻居数量 $n_{u,v}=0$。

当前进展与猜想 #

目前已经有一位厉害的学生找到了满足前5条约束（局部线性条件+前4条着色约束）的30顶点图 $G$，以及对应的正常着色 $f$ 和 $g$。但他提出了一个猜想：不存在满足所有约束条件的着色 $h$——换句话说，教授要求的那种完全符合所有条件的图，其实根本不存在。

备注：内容来源于stack exchange，提问作者Bertrand Haskell