狄拉克定理

狄拉克定理解释了图染色数与完全细分图的关系。

定理描述 
任何一个最小染色数大于等于4的图（）均存在一个4阶完全图的细分图（）。

相关背景介绍

图染色数 
对于给定的图，存在种颜色和一种染色方案，将图中每一个顶点都染成种颜色中的一种。如果染色方案满足一下条件，那么将称该染色方案为恰当的染色方案：对于图中任意两个顶点，如果，那么所染成的颜色不同。

对于图，如果存在一个种颜色的恰当染色方案，我们称是染色的。在所有满足条件的,我们称最小的那个为。

细分边 
给定一条边，在边中添加一个点使得变为一条由组成的路径，称为边的细分。

细分图 
对于图，将其中一些边进行细分而得到的图称为的细分图

色临界图 
如果对于图，其任意真子图均满足，则称为色临界图。对于任何一张图，均存在且是色临界图。

定理证明 
对图中点的数量进行递归

当的时候，的最小染色数为4，故只能为一张完全图，所以中存在的细分图（自身）。

假设当时成立，现考虑当时。由于，存在且是色临界图。由子图可知，。

由于是色临界图，不存在割点。

如果，设为的割集。根据色临界图割集的性质，且任意选择为的连通分支，为的生成子图，有。由于，所以中存在一个4阶完全图的细分图。如果，则。那么根据归纳假设，中存在4阶完全图的细分图。如果，对于的另一个连通分支，是连通图，存在一条从到的路径。则，所以是一个4阶完全图的细分图。

如果，任意选择，有。所以存在一个环。选取环上任意三个点，在中添加一个点与三条边得到新的图，则仍然有。所以对,存在三条从到内部互不相交的路径。又由于。存在环上3条内部互不相交的路径分别从到，到，到。则是图的一个子图且为4阶完全图的细分图。

Hajos 猜想 
任何一个最小染色数大于等于的图（）均存在一个阶完全图的细分图（）。

当的时候，答案是肯定的。

当的时候，答案是否定的。

对于，目前是个开放问题

参考来源 

数学定理
圖染色