在这个问题中，我给了图G = (V,E)，目标是找到具有3种颜色的图形的颜色，以最大化质量功能
q（c）=其端点颜色不同的边数。
给出一个概率3/2近似值，并表明算法返回失败（近似值较差），每个自然数k最多概率为d^-k，对于固定的d>= 1。
现在我给出了以下算法：我随机上色，这意味着边缘具有不同颜色边缘的预期概率为2/3，这使得它是3/2近似。
但是，我不知道如何证明它返回失败，最多概率为 d^-k。
可以使用一些帮助，谢谢！
，而不是尝试在此处解开量词，我只是观察到有条件期望的方法可用于证明以下确定性实现的贪婪算法正确。
存在一个未颜色的顶点时，将其颜色为邻居中最少的颜色之一。
的想法是，每个带有未颜色端点的边缘在期望中价值2/3，无论做出了哪些其他选择，假设我们将其余图形随机上色。通过使用最多样化的选择，我们至少获得了与随机价值丢失一样多的确定性价值。