[原创]图论法证明四色猜测的又一种简单方法

雷明85639720

[watermark]
               图论法证明四色猜测的又一种简单方法
                             雷  明
                      （二○一○年元月七日）
    这一方法主要是依据平面图的色数等于其同化时的最小完全同态的顶点数和平面图的最小完全同态的顶点数总是不大于4的完全图这一理论的。
    由于任意图顶点着色的色数就等于其同化时的最小完全同态的顶点数，即γ顶点＝α。若某个图的色数是γ时，则它的最小完全同态一定是一个顶点数是α＝γ的完全图Kγ（或Kα），那么现在只要能证明平面图的最小完全同态的顶点数α≤4，就能够说明四色猜测是正确的。
已知一个图中的最大团（一个最大团就是一个完全图）的边数e与其顶点数v的关系是
        e＝v(v－1)                                     （1）
按照库拉图斯基定理，平面图的边数e最大只可能是
        e＝3v－6                                       （2）
这就是当v≥3时，判别平面图与非平面图的法则。令公式（1）和公式（2）相等，则有
        3v－6＝
        6v－12＝v（v－1）
        6v－12＝v2－v
        v2－7 v＋12＝0
解该一元二次方程
        Δ＝（－7）2－4×12＝49－48＝1
        v1＝4
        v2＝3
这时的两个根均不大于4，说明平面图的最大团的顶点数是不会大于4的，也说明平面图中不会含有顶点数大于等于5的团。既然平面图中不会含有顶点数大于等于5的团，那么其最小完全同态的顶点数就一定是小于等于4的。因为平面图的色数等于其最小完全同态的顶点数，所以有任何平面图着色时4种颜就一定够用了的结论。
    到此，也就证明了平面图的四色猜测是正确的，同理，也证明了地图的四色猜测也是正确的。

                                  雷  明
                          二○一○年元月七日于长安

[/watermark]