胡延忠，罗宏芳

(1.湖北工业大学计算机学院，湖北武汉 430068;2.湖北工业大学工程技术学院，湖北武汉 430068)

1898年PETERSEN首次将Petersen图作为Peter Guthrie Tait定理的一个反例，即Petersen图不是可以1因子分解的，从而拉开了该图被广泛应用的序幕。事实上，Petersen图经常以反例的形式在图论中出现，如Petersen图不是Euler图，不是Hamilton图，不是平面图，不是二部图。Petersen图是唯一的5笼［1］，如图1所示。

图1 Petersen图

1 基础知识

下面的知识可以在文献［2-6］中找到。

定义1 图G称为一个平面图，如果G能够画在一个平面上而使得任何两条边都不相交。一个不是平面的图称为非平面图。

定义2 两个(标号)图G和H称为是同构的，如果存在V(G)到V(H)的一一对应φ，使得:uv∈E(G)当且仅当 φ(u)φ(v)∈E(H)。

定理1 (Euler恒等式)如果G是一个阶为n，边数为m和r个区域的连通平面图，则n-m+r=2。

定理2 完全图K5是非平面图。

定理3 K3，3是非平面图。

定义3 图G'称为图G的一个细分，如果有一个或多个度为2的顶点被插入到G的一条或多条边中(而得到与G'同构的图)。

定理4 (Kuratowski定理)一个图G是平面的当且仅当 G 不含 K5，K3，3，或者 K5或 K3，3的一个细分作为子图。

例题1 利用Kuratowski定理证明Petersen图是非平面图。

Petersen图以K3，3的细分作为子图，如图2所示。

图2 Petersen图以K3，3的细分作为子图

图2(a)是Petersen图去掉一条边后的同构图，图2(a)同构于图 2(b)，而图 2(b)是 K3，3的细分。由 Kuratowski定理 Petersen图是非平面图。这是一种传统的证明方法。

2 Wagner定理

定义4 对于图G和G的一条边e=uv，图G'称为是由G通过收缩边e或叠合顶点u和v而得到的图。如果G'同构于按照如下方式所获得的图:在图G-v中，连接u到v的所有邻点，且这些邻点与u不邻接。则也称G'是由G通过一次边收缩(边收缩)而得到的(对称地，G'也可以按如下方式获得:在图G-u中，连接到v的u所有与v不连接的邻点)。……