命題：一棵有n(n>=2)個葉子結(jié)點(diǎn)的樹，至少須添加ceil(n/2)條邊，就能轉(zhuǎn)變?yōu)橐粋€沒有橋的圖。或者說，使得圖中每條邊，都至少在一個環(huán)上。

證明：
這里只證明n為偶數(shù)的情況。n為奇數(shù)的證明類似。證明采用了構(gòu)造解、極端法、歸納法的方法技巧。

先證明添加n/2條邊一定可以達(dá)成目標(biāo)。

n=2時，顯然只需將這兩個葉子間連一條邊即可。命題成立。

設(shè)n=2k(k>=1)時命題成立，即S[2k]=k。下面將推出n=2(k+1)時命題亦成立。

n=2k+2時，選取樹中最長的跡，設(shè)其端點(diǎn)為a,b；并設(shè)離a最近的度>=3的點(diǎn)為a',同理設(shè)b'。

（關(guān)于a'和b'的存在性問題：由于a和b的度都為1,因此樹中其它的樹枝必然從跡<a,b>之間的某些點(diǎn)引出。否則整棵樹就是跡<a,b>，n=2<2k+2，不可能。）

在a,b間添一條邊，則跡<a,b>上的所有邊都已不再是橋。這時，將剛才添加的邊，以及aa'之間，bb'之間的邊都刪去，得到一棵新的樹。因?yàn)閯h去的那些邊都已經(jīng)符合條件了，所以在之后的構(gòu)造中不需要考慮它們。由于之前a'和b'的度>=3，所以刪除操作不會使他們變成葉子。因此新的樹必然比原樹少了兩個葉子a,b，共有2k個葉子。由歸納知需要再加k條邊。因此對n=2k+2的樹，一共要添加k+1條邊。

因此證得n/2可取。

再證明n/2是最小的解。

顯然，只有一個葉子結(jié)點(diǎn)被新加的邊覆蓋到，才有可能使與它相接的那條邊進(jìn)入一個環(huán)中。而一次加邊至多覆蓋2個葉子。因此n個葉子至少要加n/2條邊。

證畢。