条件を満たす \(X\) が存在しない必要十分条件は

• \(G\) は二部グラフである
• 各頂点 \(v\) について、頂点 \(v\) を端点とする辺を、辺が所属する二重頂点連結成分で分類した際、各グループのサイズが \(c_1,\ c_2,\ \dots,\ c_n\) になったとする。これらからいくつか選んで和をとることで \(0\) から （\(G\) における \(v\) の次数 ）\(=c_1+c_2+\dots +c_n\) までのすべての整数が作れる

です。

これを認めた場合の判定問題について考えます。まず二部グラフの判定は \(O(N+M)\) 時間でできます。 \(2\) 番目条件について、まず各頂点 \(v\) に対して \(c_1,c_2,\dots,c_n\) を取得することについてですが、これはlowlinkなどを用いて二重頂点連結成分分解を行うことで \(O(N+M)\) 時間で得られます。つぎに \(c_1,c_2,\dots,c_n\) の部分和として \(0\) から \(c_1+c_2+\dots+c_n\) まで作れるかの判定ですが、これは \(c_1 \leq c_2 \leq \dots \leq c_n\) として、 \(c_{i+1} \leq c_1+c_2+\dots +c_i + 1\) がすべての \(i\) に対し成り立つことが必要十分であることが帰納法により示せます。これはソートがボトルネックで \(O(M\log M)\) 時間でできます。以上より判定問題は \(O(N+M\log M)\) 時間で解くことができました。

では最初に述べた必要十分条件の証明に取り掛かりましょう。 必要性から証明します。

必要性

まず \(1\) 番目の条件ですが、これは \(X=(0,0,\dots,0)\) のケースについて、グラフに 奇サイクルが存在すると不可能であることから導けます。

\(2\) 番目の条件について、 各 \(v\) に対し、 \(X_u=0 (u \neq v)\) のとき、向き付けが存在するような \(X_v\) の条件を考えます。 頂点 \(v\) と辺で結ばれる \(2\) 頂点 \(a,\ b\) について、頂点 \(v,\ a,\ b\) を通るような単純サイクルが存在するとき、 \(2\) 辺 \((v,\ a),\ (v,\ b)\) の向き付けは同じ向きになります。このことから頂点 \(v\) を端点とする辺は二重頂点連結成分で分類され、これらからいくつか選んで和をとることで \(0\) から \(c_1+c_2+\dots +c_n\) のすべての整数が作れることが必要です。

十分性

十分性について、まず木の場合は必要十分条件を満たしており、実際にすべての \(X\) に対して条件に対応する向き付けを与えることができることを確認しましょう。向き付けを与える際は適当な頂点を根として根付き木とみなし、根側から向きをつけていきます。頂点 \(v\) に着目したとき、 \(v\) を端点とする辺のうちね側の辺だけ向き付けられています。 このときこの辺の向きに合わせて各辺の向きを決めることで \(X_v\) に入次数か出次数がひとしくなるようにできます（例えば \(X_v=1\) ならば残りの辺を根側の辺と反対の向きに向き付けることで条件を満たします）。

では一般の場合はどうでしょうか？実はこの場合も二重頂点連結成分が木構造をなすこと（block-cut tree）からほとんど同じ要領で構築が可能です。木の場合における辺に対しては二重頂点連結成分の辺集合が対応しており、木の場合と同じようにやるにはこれらの辺が端点に着目した際向きがそろっているように向き付けなければなりませんが、これは \(G\) が二部グラフであることから可能です。