ひとつ頂点を消すと偶数個の辺が消える. ということはもともとの辺の数は偶数でなければならない. すなわち, 頂点数は奇数である必要がある.

木を根付き木と考え, 根の子とその子を根とする部分木を考える.

部分木の頂点数が奇数の場合は, この部分木を親と切り離さないといけないので, 親を先に消す必要がある.

部分木の頂点数が偶数の場合は, 逆に親を先に消してはならず, 部分木の方を先に消す必要がある.

よって, まず部分木の頂点数が偶数の部分木を消し, 次に親を消し, 残りの部分木を消すという手順となる.

これを再帰的に行うことですべての頂点を消すことができる.