有没有人对一个非正式的证明感兴趣，证明图的顶点三色问题是NP完全的？
不久前，在关于整数线性规划的讨论中，我提到过图顶点三色问题（G3C）、可满足性问题（SAT）和整数因式分解（FAC）之间相对难度的评论。这条评论得到了几票赞，但几乎肯定只是因为它清晰明确地阐述了这些问题之间的联系，并将散落在其他回复中的观点汇集在一起。
但是……有没有人对看到一个相对完整的证明，证明G3C是NP完全问题（NPC）感兴趣呢？
查看原文
A short time ago, in the discussion about Integer Linear Programming, I made a comment[0] about the relative hardness of Graph Vertex 3-Colouring (G3C), Satisfiability (SAT), and Integer Factoring (FAC). That got a few upvotes, but almost certainly just because it made clear and explicit the connections, and gathered together the ideas scattered through other replies.<p>But ... would anyone be interested in seeing a relatively complete proof that G3C is NPC?<p>https://news.ycombinator.com/item?id=44278725