命題：一棵有n(n>=2)個葉子結點的樹，至少須添加ceil(n/2)條邊，就能轉變為一個沒有橋的圖。或者說，使得圖中每條邊，都至少在一個環上。

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

先證明添加n/2條邊一定可以達成目標。

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

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

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

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

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

因此證得n/2可取。

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

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

證畢。