到目前为止，关于图运算的定义在不同的图论书中还很不统一。请读者注意区分！

   一）关于删边、点，收缩、加新边

  设G=<V,E>为无向图

(1)设e(-E,用G-e表示从G中去掉边e,称为删除e.又设E'为E的真子集，用G-E'表示从G中删除E'中的所有边，称为删除E'.(2)设v(-V,用G-v表示从G中去掉v及v关联的一切边，称为删除顶点v.又设V'为V的真子集，用G-V'表示从G中删除V'中的所有顶点，称为删除V'.

(3)设e=(u,v)(- E,用G\e表示从G中删除e，将e的两端点u,v用一个新的顶点w代替，使w关联除e外的u,v关联的一切边，称为边e的收缩.[有的书上记为G*e],收缩时，w也可取为u 或 v.

(4)设u,v(- V,(u,v可能相邻，也可能不相邻），用GU(u,v),[或G+(u,v)]表示在u,v之间加一条边（u，v),称为加新边.

  简单图经过边的收缩或加新边后，可变成非简单图。除此，还有并图、交图、差图、环和、联图与积图等，略去。

  二）插入2次顶点与消去2次顶点

  设e=(u,v)为图G中的一条边，在G中删除e,增加新的顶点w，使u,v均与w相邻，即G'=（G-e)U{(u，w),(w,v)},称为在G中插入2度顶点w;设w为G中一个2度顶点，w与u,v相邻，删除w，增加新边（u,v),即G'=（G-w)U{(u,v)},称为在G中消去2度顶点w.

  删除一边{u,v}，且添新点w和{u，w}与 {w,v}的过程也有的书上称为初等细分。顺便给出同胚定义：若两个图G'与 G"是同构的，或通过反复插入或消去2度顶点后是同构的，则称G'与 G"是同胚的。与此概念有关的库拉图斯基定理：图G是平面图当且仅当不含与K(5)同胚子图，也不含与K(3,3)同胚的子图。图G是平面图当且仅当G中没有可以收缩到K（5）的子图，也没有可以收缩到K（3,3）的子图。

  三）图论中须明确的概念及常用的定理

 着色：对无环图G顶点的一种着色，是指对它的每一个顶点涂上一种颜色，使得相邻的顶点涂不同的颜色。若能用k种颜色给G的顶点着色，就称对G进行了k着色，也称G是k-（而不管是否都用到）可着色，若G是k-可着色的，但不是（k-1)-可着色的，就称G是k-色图，称这样的k为G的色数，记为X(G)=k.

  极大平面图：设G为简单平面图，若在G的任意不相邻的顶点u,v之间加边（u，v），所得图为非平面图，则称图G为极大平面图。

  定理1：设G是简单平面图，则G中至少存在一个顶点其度数<、= 5.

  定理2：奇圈和奇数阶轮图都是3-色图，而偶数阶轮图为4-色图。

  定理3：X（Kn）=n.

  定理4：设G为n阶（n>、=3）m条边的极大平面图，则m=3n-6.

  定理5：（Heawood)任何平面图都是5-可着色的。

  证：仍设G是连通的简单平面图。设5颜色分别用1,2,3,4,5所代表，并且Vi表示涂色i的顶点，i=1,2,3,4,5.仍对n作归纳法。

（1）n<、=5时，结论显然。

（2）设n=k(k>、=5）时结论成立，n=k+1时如下证明。由定理1.可知，存在v(-V(G),d(v)<、=5.设G’=G-v，则G'是k阶图，由归纳假设可知，G'是5-可着色的，下面的证明将G'还原成G时，v是可着色的。

1）若d(v)<5,v的着色无问题。

2）若d(v)=5,但与v相连的顶点在G'的着色中至多用了4种颜色，v的着色也无问题。

3）若d（v)=5,且与v相邻的5个顶点在G'的着色中已经用了5种颜色，这样v的着色就成了问题。解决办法如下。

 设V1,3={V|在G'的着色中V着1或3}，并且G1,3=G[V1,3].

(a)若V1与V3属于G1,3的不同连通分支，则将V1所在的连通分支中，1,3两种颜色互换，于是V1涂颜色3，腾出1来给v着色，见图1.（a)、(b)。

            1

           /  \

     v1--3/    3

v5---v---v2

    /  \

v4       v3--1--3

             |  |

             3  1

    图1.（a)

            3

           /  \

     v3--1/    1

v5---v---v2

    /  \

v4       v3--1--3

             |  |

             3  1

    图1.(b)

(b)若V1与 V3在G1,3的同一个连通分支中，此时，G[V1,3U{v}]含回路C，v在C上，除v外，在C上的顶点涂1与涂3的顶点交替出现。再令V2,4={V|V在G'中的涂颜色2或4},G2,4=G[V2,4]，由于C的隔离，V2，V4必在G2,4的不同的连通分支中，在V2所在的连通分支中，将颜色2,4互换，腾出颜色2给v涂色，见图2.（a)、(b)（略）.

  1879年Kempe自称用定理1及换顶点颜色的方法证明了四色猜想，即任何平面图都是4-可着色的，1890年希伍德举出了25阶的反例说明Kempe的证明是不对的，而他本人证明了5色定理，到目前为止，四色猜想没有得到彻底的解决。若四色猜想得到证明，关于平面的着色理论就得到了最好的解决，因为对任何的偶数阶轮图Wn（n>、=4），有X(Wn)=4.【1】

参考资料：【1】耿素云，屈婉玲，王捍貧编著  ， 2002年6月，《离散数学教程》，北京：北京大学出版社。