以下では始点が \(a\) 終点が \(b\) である辺を \((a,b)\) と表記する．また，\((a,b)\) と \((b,a)\) をまとめて \([a,b]\) と表記する．

まず，与えられるグラフがトーナメントである場合を考える．

以下の補題を用いる．

補題：ある四頂点 \(a,b,c,d\) に対して、\([a,b],[b,c],[c,d],[d,a]\) のみを反転することができる．

補題の証明：\(a,b,c,d\) を含まないサイズ \(K-2\) の部分集合 \(X\) を一つとる．\(S=X\cup \lbrace a,b \rbrace,X\cup \lbrace b,c \rbrace,X\cup \lbrace c,d \rbrace,X\cup \lbrace d,a \rbrace\) の順に操作をすればよい．（証明終わり）

\(K\) が偶数のとき，以下の補題 2 を用いて数学的帰納法を回すことで常に答えが Yes であることがわかる．

補題 2：\(K\) が偶数のとき，ある三頂点 \(a,b,c\) に対して、\([a,b],[b,c]\) のみを反転することができる．

補題 2 の証明：\(a,b,c\) を含まないサイズ \(K-2\) の部分集合 \(Y\) を一つとる．\(Y\cup\lbrace a,b\rbrace ,Y\cup \lbrace b,c\rbrace\) として順に操作を行う．このとき反転してる辺は \([a,b],[b,c]\) を除くと \(a,c\) を片方の端点，もう片方を \(Y\) に含まれる頂点とした完全二部グラフをなす．この完全二部グラフは（\(|Y|=K-2\) が偶数であることから）何個かの長さ \(4\) のサイクルに分解できる．よって補題を用いることで \([a,b],[b,c]\) のみを反転できる．（証明終わり）

\(K\) が奇数のとき，操作によって各頂点の出次数の偶奇が変化しないことから，出次数が偶数の頂点の個数が \(\lceil \frac{N}{2}\rceil\) 個であることが答えが Yes となるための必要条件である．

実は，これが十分条件でもあることが，補題を用いて数学的帰納法を回すことで証明できる．

入力がトーナメントでない場合，入力の補グラフを取り（ただし補グラフは無向グラフとする），現時点での各頂点の（入力のグラフの）出次数の偶奇を白黒に対応させると，以下の問題に帰着される．

\(N\) 頂点のグラフが与えられ，各頂点には白か黒の色がついている．各辺について、どちらかの頂点の色を反転するという操作を行う．黒の頂点数を指定された個数にできるか判定．

グラフが連結な場合を考える．全域木を取り，木に含まれない辺は根方向に向き付けることを考えると，根以外は自由に色を決められる．また，出次数の総和が一定なことから，根以外の色を決めたとき根の色は一意に定まる．このことから，色を変更できる頂点数の偶奇のみが定まっていることが分かる．(類題：AGC 035-B Even degrees)

グラフが非連結な場合も連結成分ごとに上の処理を行い，総和を所定の値にできるか判定できれば良い．

必要なのは補グラフの各連結成分の頂点数と辺数のみであり，補グラフ BFS で求めることができる．

（更に考察を進めると，入力のグラフが密でない場合必ず答えが Yes となることがわかり，補グラフBFS を愚直に行っても問題ないことが言える．）