论文部分内容阅读
图中可缩边与可去边是探讨图的结构,寻求用归纳法证明图的某些性质的一个有利工具。研究一个图中可缩边与可去边的存在性及它们的分布情况,具有很重要的理论价值。尹建华对4-连通图G的可去边定义了以下运算:(1)从G中去掉E得图G-E。(2)如果E的某个端点在G中度数为3,则去掉此端点,再两两连接此端点在G-E中的3个邻点。(3)如果通过运算(2)后有多重边出现,则用单边代替它们,使此图成为简单图。经过上述运算后,若得到的图仍为4-连通图,则称E为G的可去边,否则称为G的不可去边。尹建华证明了4-连通图G(阶数为5和6的2循环图除外)中总存在可去边,并给出了可去边与可收缩边的一个下界,但文中没有给出可去边数的下界。在这篇文章中,我们证明了对于每一个阶数大于或等于6的4-连通图(阶数为6的2循环图除外),至少有[(4|G|+16)/7]条边,并且刻化了达到这一下界的图的结构。