頂点 \(1\) を根とする根付き木を考える. この木を深さが偶数の頂点と奇数の頂点に分けると, どちらかは必ず \(N/2\) 個以上の頂点を含むので, \(N/2\) 個以上の方から \(N/2\) 個を取り出す.