グラフ上のゲームで、隣接頂点への移動などを扱う際には、しばしばグラフのマッチングを考えることが有効です。この問題も例に漏れません。

結論から言えば

\[\text{Bob が勝つ}\iff \text{木が完全マッチングを持つ}\]

です。木の完全マッチングの存在判定は、葉に接続する辺を貪欲に採用する、というアルゴリズムによって \(O(N)\) 時間で行うことができます。

以下、証明を行います。

\((\impliedby)\) 木の完全マッチングを取ります。Alice が印をつけた次の手番では、Bob は直前に Alice が印をつけた頂点にマッチしている頂点を選んで印をつければ良いです。

\((\implies)\) 対偶を示します。木が完全マッチングを持たないとき、Alice が勝つことを示します。適当に根 \(r\) を取り、根付き木にします。木の最大マッチングを、葉に接続するを貪欲に採用するアルゴリズムで解く方法を観察しましょう。空のマッチングから始めて、深さの深い頂点から順に、次のことを行うのでした。

• その頂点がすでにマッチングに含まれていれば、なにもしない。
• そうでなく、その頂点の親が存在し、その親がまだマッチングに含まれていなければ、その親とマッチさせる。
• 上記のいずれでもない場合、その頂点は最大マッチングに含まれない。

疑似コードで書くと、次のようになります。yet は頂点 v があと何回使えるかを表しています。matching(v) は貪欲にマッチングをとったときに頂点 v が余るかどうかを返します。

# matching(r) == 0 iff tree has perfect matching
int matching (int v) :
    yet = 1
    for c in child of v :
        yet -= matching(u)
    if yet < 0 :
        # not perfect matching
        return inf
    else :
        return yet

木が完全マッチングを持たない場合、疑似コードで matching(r) を実行すると、次のいずれかの場合に分かれます。

• 1 が返る場合
• if yet < 0 の分岐に入る場合

前者の場合は、Alice ははじめに頂点 \(r\) を選ぶと、勝つことができます。木から \(r\) を取り除いたグラフは、完全マッチングを持つため、先手と後手が入れ替わったとして \((\impliedby)\) と同じ議論をすれば、Alice が必勝であることが示せます。

後者の場合を考えます。はじめて if yet < 0 の分岐に入るタイミングがあるので、そのときの v を取ります。また、 \(v\) の子 \(c\) であって、 matching(c) が \(1\) を返した頂点を適当に \(2\) つ取り \(c_1,c_2\) とします（ yet < 0 の分岐に入るので、そのような頂点は \(2\) つ以上存在します）。このとき、Alice ははじめに \(c_1\) を選ぶと、勝つことができます。 \(c_1,c_2\) の部分木と \(v\) を合わせたグラフ \(G\) に注目すると、 \(G\) から \(c_1\) を取り除いたグラフは完全マッチングを持つため、先ほどと同様に先手と後手が入れ替わった議論をすると、 \(G\) の中で初めて着手できなくなるのは Bob であることがわかります。しかし、木全体と \(G\) の境界はまさに頂点 \(v\) であり、 \(v\) には Bob の印が付くことになります。はじめて \(G\) の外の頂点に印をつける際は、頂点 \(v\) に辺で繋がっている頂点に印をつけなければならないため、Bob は着手できずに負けてしまいます。したがって、この戦法は Alice の必勝法を与えています。

以上で \(\implies\) も示されました。