, , , , ,

, ，d(

)=G,G

7 7 v0

v1v2

v3v4

v5v6v7v8 v0

不含T作为子图，我们说明G必含T*作为子图,现按G值分类讨论。

（1）

7 7

G3。此时G=8-G8-3=5。当G=7或8时,显然G必含T作为子图。当G=dv0=6时，因G5，v7至少与v1、v2、v3、v4、v5、v6中四个顶

点相邻。无论v、 是否相邻，G必含 作为子图。

G

v1 6

v7 v8

当G

=dv0=5时，G为9阶5-正则图，由Euler定理2eG=95，此为不可能，



所以G必含T7作为子图。

（2）

G=dv0=4。此时G=8-G=8-4=4。

v0

G

v1 v2 v3 v4

v5 v6 v7 v8

当v5、v6、v7、v8在G中互不相邻时，若v1、v2、v3、v4互不相邻，因G=4，则在G中v至少与 、 、 、 中一个顶点相邻，所以G必含 作为子图