给定图
，我们称
是它的一个合法
-染色，如果赋给每个点个颜色中的一个，并且没有任何一条边的两个端点是同色的。给定一个染色和一个顶点
，令)
为点
处可用的颜色的集合，即在染色下没有出现在的邻居的颜色集合。
证明存在一个正整数
使得对任意整数
，以下命题成立：对任意的没有三角形且最大度数为
的图)
，以及它的任意一个顶点,
![\mathbb{E}_{\sigma}[|L_G(v)|] \geq d/3,](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D_%7B%5Csigma%7D%5B%7CL_G(v)%7C%5D%20%5Cgeq%20d%2F3%2C)
这里是一个符合均匀分布的随机合法-染色。
证：
我们希望证明在无三角形的图中，任意顶点的邻居集合)
的颜色数量%7C)
的期望值与顶点的度数之间的关系。
1. 定义和设定
设)
，表示顶点的度数。我们使用随机变量
表示邻居中选择颜色
的顶点数量。我们希望计算，即颜色集合的大小。
2. 颜色选择的概率
对于每个邻居)
，我们设定颜色选择是独立的。对于每个颜色，邻居选择该颜色的概率为%20%3D%20%5Cfrac%7B1%7D%7Bd%7D)
。
因此，邻居
和
同时选择颜色的概率为：
%20%3D%20P(B_%7Bi_1%7D)%20%5Ccdot%20P(B_%7Bi_2%7D)%20%3D%20%5Cfrac%7B1%7D%7Bd%7D%20%5Ccdot%20%5Cfrac%7B1%7D%7Bd%7D%20%3D%20%5Cfrac%7B1%7D%7Bd%5E2%7D)
。
但由于图是无三角形的，和不会直接相连，因此它们的选择是相互独立的。
3. 期望值的计算
我们计算的期望值![\mathbb{E}[|L_{\sigma}(v)|]](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5B%7CL_%7B%5Csigma%7D(v)%7C%5D)
。我们先定义指示随机变量：
因此，期望值可以表示为：
![\mathbb{E}[|L_{\sigma}(v)|] = \sum_{j} \mathbb{E}[X_j]](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5B%7CL_%7B%5Csigma%7D(v)%7C%5D%20%3D%20%5Csum_%7Bj%7D%20%5Cmathbb%7BE%7D%5BX_j%5D)
。
利用线性期望，我们可以得到：
![\mathbb{E}[X_j] = 1 - P(\text{没有邻居选择颜色 } j)](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5BX_j%5D%20%3D%201%20-%20P(%5Ctext%7B%E6%B2%A1%E6%9C%89%E9%82%BB%E5%B1%85%E9%80%89%E6%8B%A9%E9%A2%9C%E8%89%B2%20%7D%20j))
。
对于每个邻居，没有选择颜色的概率为
。因此，所有邻居都不选择颜色的概率为：
%20%3D%20%5Cleft(%20%5Cfrac%7Bd-1%7D%7Bd%7D%20%5Cright)%5Ed)
。
于是，
![\mathbb{E}[X_j] = 1 - \left( \frac{d-1}{d} \right)^d](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5BX_j%5D%20%3D%201%20-%20%5Cleft(%20%5Cfrac%7Bd-1%7D%7Bd%7D%20%5Cright)%5Ed)
。
4. 期望值的综合
将其代入期望值的表达式中：
![\mathbb{E}[|L_{\sigma}(v)|] = \sum_{j} \left( 1 - \left( \frac{d-1}{d} \right)^d \right).](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5B%7CL_%7B%5Csigma%7D(v)%7C%5D%20%3D%20%5Csum_%7Bj%7D%20%5Cleft(%201%20-%20%5Cleft(%20%5Cfrac%7Bd-1%7D%7Bd%7D%20%5Cright)%5Ed%20%5Cright).)
如果我们假设有
种颜色，则期望值为：
![\mathbb{E}[|L_{\sigma}(v)|] = c \left( 1 - \left( \frac{d-1}{d} \right)^d \right)](https://math.jianshu.com/math?formula=%5Cmathbb%7BE%7D%5B%7CL_%7B%5Csigma%7D(v)%7C%5D%20%3D%20c%20%5Cleft(%201%20-%20%5Cleft(%20%5Cfrac%7Bd-1%7D%7Bd%7D%20%5Cright)%5Ed%20%5Cright))
。
5. 不等式的验证
为了确保至少为
，我们需要选择适当的和。通过适当选择颜色数量和最大度数，我们可以使得：
%5Ed%20%5Cright)%20%5Cgeq%20%5Cfrac%7Bd%7D%7B3%7D)
。
通过计算和选择合适的和，可以验证上述不等式成立。
综上，在无三角形的图中，任意顶点的邻居集合的颜色数量的期望值与顶点的度数之间的关系得到了证明。
