この問題の本質は、期待値の線形性(および、どの頂点も最大で1回しか選ばれないこと)により次の事実が言えることにあります。

• 操作回数の期待値は次と等しい: 各頂点について「グラフが空になるまでにその頂点を選択する確率」を求め、総和を取ったもの。

よって、「グラフが空になるまでにその頂点を選択する確率」について考えればよいです。

ここで、次の \(2\) つの事実が証明できます。頂点 \(v\) に到達可能な頂点集合を \(S(v) \subseteq V\) とします。

• \(S(v)\) に含まれる頂点を選んだ時、またその時のみに頂点 \(v\) は削除される。
• \(S(v)\) に含まれない頂点を選んだときに、\(S(v)\) に含まれる頂点が削除されることはない。

つまり、グラフが空になるまでに \(v\) を選択する確率は、\(S(v)\) の中で初めて選択された頂点が \(v\) である確率に等しく、これは \(\frac{1}{|S(v)|}\) です。

以上より、この問題の答えは \(\sum_{v \in V} \frac{1}{|S(v)|}\) です。