命题：一棵有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条边。

证毕。