1. 概要
Undirected Vertex Geography は，無向グラフ上で駒を動かす $2$ 人ゲームです．各手番では，現在駒がある頂点から隣接する頂点に駒を移動させます．ただし，選べる頂点は，一度も駒が置かれたことがない頂点に限ります．動けなくなったプレイヤの負けです．
本記事では，Undirected Vertex Geography の必勝戦略が最大マッチングを用いて記述できることを証明します．
2. 前提知識
グラフ理論の用語，特にマッチングに関する用語を用います（参考：グラフ理論用語集）．
「関連問題」を解く上ではさらにマッチングに関する知識（例えば最大マッチングを求めるアルゴリズム）が必要となることがありますが，本記事を理解する上では直接は必要ありません．
3. 問題設定
3.1. 問題
無向グラフ $G = (V, E)$ と，開始頂点 $v_0 \in V$ が与えられます．頂点 $v_0$ に駒を置き，先手からゲームを開始します．各手番では，その時点で駒がある頂点と隣接する頂点をひとつ選び，選んだ頂点へ駒を移動させます．ただし，選べる頂点は，一度も駒が置かれたことがない頂点に限ります．そのような移動を行えなかったプレイヤの負けとなります．
$G$ および $v_0$ が与えられたとき，このゲームが先手，後手のどちらに必勝法があるかを求めてください．
このゲームを Undirected Vertex Geography と呼びます．なお Geography という名称は，地名をしりとりのようにつないでいく遊びに由来します．
3.2. 具体例
次の図のグラフ $G$ および開始頂点 $v_0$ の場合に，先手，後手のどちらに必勝法があるかを求めてください．
問題の答え
先手に必勝法があります．
適当な場合分けによっても証明できますが，複雑な場合分けの要らない簡潔な証明もあります．そのような証明が分からなかった場合には，4 節の議論を理解した上で改めて考えてみてください．
3.3. 素朴な解法
ゲームの途中経過としては，
- 一度駒が置かれたことがある頂点全体の集合 $S$
- 駒が置かれている頂点 $v$
の組 $(S, v)$ を状態として考えることができます．同じ状態に至るまでの手順の違いなどは，それ以降の展開に影響しません．
したがって $S$ について降順に，各状態 $(S, v)$ について手番のプレイヤに必勝法があるか否かを求めていく dp により 【問題 1】 を解くことができます．グラフの頂点数を $N$ として，$\mathrm{O}(N ^ 2 \cdot 2 ^ N)$ などの計算量となります．
ある程度競技プログラミングに慣れている方にとっては，比較的簡単に思い浮かびやすい解法でしょう．しかしこのようにゲームの途中経過としてありうる状態をすべて考えるという方法では，計算量が $N$ について指数時間になってしまいます．
実は 【問題 1】 は $N$ に関する多項式時間の計算量で解くことができます．このことの証明が本記事のテーマです．
4. 解法
4.1. 結論
まず，用語や記号について準備します．
マッチング $M$ と頂点 $v$ に対して，$v$ が $M$ のある辺の端点であるとき，$v$ は $\boldsymbol{M}$ 飽和，そうでないとき，$v$ は $\boldsymbol{M}$ 非飽和 であるといいます．辺 $uv$ がマッチング $M$ に含まれるとき，$v$ は $u$ に（あるいは $u$ は $v$ に）マッチしているといいます．
この定理から，【問題 1】 は $G$ の頂点数を $N$ として，例えば $\mathrm{O}(N ^ 3)$ 時間などの計算量で解けることが分かります．（計算量は最大マッチングを求めるアルゴリズム次第です．）
以下，この定理を証明します．
正整数 $i$ について，$v_0$ を除いて $i$ 番目に選ぶ頂点を $v_i$ と書くことにします．したがって，ゲームは次のように進行します．
- $v_0$ が与えられる．
- 先手が $v_1$ を選ぶ．
- 後手が $v_2$ を選ぶ．
- 先手が $v_3$ を選ぶ．
- 後手が $v_4$ を選ぶ．
- $\vdots$
4.2. 先手勝ちの証明
【問題 1】 において $v_0$ が非飽和である最大マッチングが存在しないならば，先手に必勝法がある．
最大マッチングをひとつとり，$M$ とします．先手は，次の戦略をとることで勝てることを証明します．
- 先手の戦略：直前に後手番で選ばれた頂点 $v_{2k}$ （または最初に与えられた頂点 $v_0$）と $M$ でマッチしている頂点を選ぶ．
この戦略が常に実行可能であることを証明します．そのためには，$v _ {2k}$ が $M$ 飽和であることと，$v _ {2k}$ と $M$ でマッチする頂点がこの時点で選ばれていないことを証明すればよいです．
先手の戦略から，$v_0, v_1, \ldots, v_{2k}$ まで選ばれた時点では，
$$ v_0v_1, \quad v_2v_3, \quad \ldots, \quad v _ {2k-2} v _ {2k-1} $$
はすべて $M$ に含まれます．
$v_{2k}$ が $M$ 非飽和であると仮定します．すると $M$ から
- $0 \leq i < k$ に対して辺 $v _ {2i} v _ {2i+1}$ を削除し，
- $0 \leq i < k$ に対して辺 $v _ {2i+1} v _ {2i+2}$ を追加する
ことで，$M$ と辺の個数が同じマッチング $M'$ であって，$v_0$ が非飽和であるものが得られます．$M$ が最大マッチングであることから $M'$ も最大マッチングとなりますが，これは $v_0$ が非飽和である最大マッチングが存在しないという仮定に反します．
以上より，$v _ {2k}$ は $M$ 飽和です．
最後に，$v _ {2k}$ と $M$ でマッチする頂点がこの時点で選ばれていないことを示します．
$$ v_0v_1, \quad v_2v_3, \quad \ldots, \quad v _ {2k-2} v _ {2k-1} $$
が $M$ の辺であり，$v _ {2k} \neq v_i$ ($0\leq i< 2k$) なので，$v _ {2k}$ が $v_0,v_1,\ldots,v_{2k-1}$ とマッチすることはありません．したがって，$v _ {2k}$ と $M$ でマッチする頂点はこの時点で選ばれていません．
以上により，$v_0$ が非飽和である最大マッチングが存在しないならば，先手に必勝法があることが示されました． $\blacksquare$
4.3. 後手勝ちの証明
【問題 1】 において $v_0$ が非飽和である最大マッチングが存在するならば，後手に必勝法がある．
そのような最大マッチングをひとつとり，$M$ とします．後手は，次の戦略をとることで勝てることを証明します．
- 後手の戦略：直前に先手番で選ばれた頂点 $v_{2k+1}$ と $M$ でマッチしている頂点を選ぶ．
この戦略が常に実行可能であることを証明します．そのためには，$v _ {2k+1}$ が $M$ 飽和であることと，$v _ {2k+1}$ と $M$ でマッチする頂点がこの時点で選ばれていないことを証明すればよいです．
後手の戦略から，$v_0, v_1, \ldots, v _ {2k}, v _ {2k+1}$ まで選ばれた時点では，
$$ v_1v_2, \quad v_3v_4, \quad \ldots, \quad v _ {2k-1} v _ {2k} $$
はすべて $M$ に含まれます．
$v _ {2k+1}$ が $M$ 非飽和であると仮定します．$v_0$ も $M$ 非飽和であったことから，$M$ から
- $0 \leq i < k$ に対して辺 $v _ {2i+1} v _ {2i+2}$ を削除し，
- $0 \leq i \leq k$ に対して辺 $v _ {2i} v _ {2i+1}$ を追加する
ことで，$M$ より辺が $1$ 個多いマッチング $M'$ が得られます．これは $M$ が最大マッチングであることに反します．
以上より，$v _ {2k+1}$ は $M$ 飽和です．
最後に，$v _ {2k+1}$ と $M$ でマッチする頂点がこの時点で選ばれていないことを示します．まず $v_0$ は $M$ 非飽和なので $v _ {2k+1}$ と $v_0$ はマッチしません．また
$$ v_1v_2, \quad v_3v_4, \quad \ldots, \quad v _ {2k-1} v _ {2k} $$
が $M$ の辺であり，$v _ {2k+1} \neq v_i$ ($0\leq i\leq 2k$) なので，$v _ {2k+1}$ が $v_1,v_2,\ldots,v_{2k}$ とマッチすることもありません．したがって，$v _ {2k+1}$ と $M$ でマッチする頂点はこの時点で選ばれていません．
以上により，$v_0$ が非飽和である最大マッチングが存在するならば，後手に必勝法があることが示されました． $\blacksquare$
【補題 4】，【補題 5】 より，【定理 3】 が示されました．
5. 関連問題
- https://www.codechef.com/problems/HAMILG
- https://qoj.ac/contest/1070/problem/5250
- https://codeforces.com/contest/1710/problem/E
- https://atcoder.jp/contests/fps-24/tasks/fps_24_s
- https://atcoder.jp/contests/waipc-qual/tasks/waipc_qual_b
- https://atcoder.jp/contests/ttpc2024_2/tasks/ttpc2024_2_n
- https://codeforces.com/contest/1147/problem/F
問題について
1, 2 はおおよそ本記事の通りの勝敗判定が直接問われている問題です．ただし最大マッチングを求めるアルゴリズムが必要で，特に 1 は二部グラフではない一般グラフの問題なので難易度は高めです．
3 も UVG の勝敗判定に関する問題ですが，グラフが巨大なので，通常の最大マッチングアルゴリズムは使えず，難易度は高いです．
4, 5 は UVG の勝敗判定を踏まえた数え上げや最適化の問題です．
6, 7 は UVG と似た設定の問題です（直接関係があるわけではありません）．これらの問題の結論もマッチングを用いて記述されますが，特に 7 は単純な最大マッチングに関するものではなく，かなり難しいと思います．
6. まとめ
この記事では，Undirected Vertex Geography の勝敗が最大マッチングによって特徴付けられることを示しました．具体的には，開始頂点 $v_0$ が後手勝ちであることと，$v_0$ が非飽和である最大マッチングが存在することが同値です．
証明では，マッチングに含まれる辺と含まれない辺が交互に現れるパス（交互パス）上で，マッチングの辺をずらすという議論が現れました．これはマッチングの理論では基本的な手法で，多くの最大マッチングを求めるアルゴリズムにも現れます．また，交互パスの存在によって最大マッチングを特徴づける Berge の定理も重要です．
なお，Undirected Vertex Geography には，「グラフを有向グラフにする」「頂点ではなく，同じ辺を複数回選ぶことを禁止する」など，いくつかの変種が存在しますが，
- Undirected Edge Geography
- Directed Vertex Geography
- Directed Edge Geography
はいずれも PSPACE-complete と呼ばれる計算量クラスに属する問題であることが知られており，$N$ に関する多項式時間計算量で解く方法は知られていません．
7. 参考文献
- Wikipedia．Word chain．https://en.wikipedia.org/wiki/Word_chain．（閲覧日: 2026-03-19）．
- Wikipedia．Generalized geography．https://en.wikipedia.org/wiki/Generalized_geography．（閲覧日: 2026-03-19）．
- Aviezri S. Fraenkel, Edward R. Scheinerman, Daniel Ullman．Undirected edge geography．Theoretical Computer Science．Vol. 112．No. 2．pp. 371–381．1993．DOI: 10.1016/0304-3975(93)90026-P．https://doi.org/10.1016/0304-3975(93)90026-P．
- David Lichtenstein, Michael Sipser．GO Is Polynomial-Space Hard．Journal of the ACM．Vol. 27．No. 2．pp. 393–401．1980．DOI: 10.1145/322186.322201．https://doi.org/10.1145/322186.322201．
トップページ：AtCoder Algorithm Lectures
