algorithm - 没有 3-clique 的图形至少需要 4 种颜色

Question

给出一个具有以下属性的图的例子。 (请注意，您需要给出单个图表作为答案。)

该图不包含三角形(即 3 个顶点的团)作为子图。图形至少需要 4 种颜色才能正确着色顶点[如果您认为这样的图是不可能的，请证明该陈述。]

1.明天我们有期末考试，这道题可能会出现在试卷上。2.我认为不可能画出这样的图。但是如何证明呢？非常感谢你。

Answer 1

网络搜索发现 https://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph

Grötzsch 图是无限无三角图序列的成员，每个图都是序列中前一个图的 Mycielskian，从空图开始； Mycielski (1955) 使用这个图序列来证明存在具有任意大色数的无三角形图。因此，Grötzsch 图有时也称为 Mycielski 图或 Mycielski–Grötzsch 图。与此序列中后来的图不同，Grötzsch 图是具有色数的最小无三角形图 (Chvátal 1974)。