海南省三亞市學(xué)院理工學(xué)院 翟冬陽

一、介紹

本文所研究的圖都是簡(jiǎn)單有限圖。設(shè)G是一個(gè)圖，E(G)和V（G）分別表示G的邊集和頂點(diǎn)集。設(shè)表示由X誘導(dǎo)的子圖，Gx和GX分別表示由誘導(dǎo)的子圖，表示x的鄰點(diǎn)集。我們用表示階完全圖，表示的補(bǔ)圖，“+”表示兩個(gè)圖的交。本文未注釋的標(biāo)記參考[1]。

圖是2樹當(dāng)且僅當(dāng)G=K3，或者G中存在一個(gè)度為2的點(diǎn)v，使得與v相鄰的兩個(gè)點(diǎn)也相鄰，且Gv是一個(gè)2樹。我們把2樹中度為2的點(diǎn)稱為耳朵，顯然，一個(gè)2樹至少有兩個(gè)耳朵。關(guān)于2樹還有下面的性質(zhì)：

二、證明

為了證明定理1.1，我們首先證明下面的引理：

[1] Bondy J A, Murty U S R． Graph Theory with Application[M]．London and Basingstoke： The Macmillan Press Ltd，1976．