以下の解説では頂点 \(u,v\) を結ぶ辺を \((u,v)\) などと表します。

頂点数が偶数の場合

まず頂点数が偶数で \(2N\) である場合を考えます。辺彩色数は明らかに \(2N-3\) 以上ですが、実はつねに \(2N-3\) を達成できます。これはグラフの \(2N-3\) 個の完全マッチングへの分解を与えれば示せます。

補グラフの各連結成分はサイクルになっていることに着目します。

まず各サイクルの長さがすべて偶数の場合を考えましょう。このとき補グラフは \(N+N\) 頂点の二部グラフと考えることができ、元のグラフの辺は

• 左側 \(N\) 頂点からなるクリーク内の辺(1)
• \(N+N\) 頂点で各頂点の次数が \(N-2\) の正則二部グラフの辺(2)
• 右側 \(N\) 頂点からなるクリーク内の辺(3)

の \(3\) つに分けることができます。

\(N\) が偶数の場合、(1),(3) の辺はそれぞれ \(N-1\) 個の完全マッチングに分解することができます（たとえばhttps://en.wikipedia.org/wiki/Graph_factorization に書かれています）。これらを左右で組み合わせることで \(N-1\) 個の完全マッチングが得られます。残りの(2)の辺についても正則二部グラフは Hall の定理から常に完全マッチングに分解できるることがわかり、 \(N-2\) 個の完全マッチングに分解することができます。以上によりグラフの \(2N-3\) 個の完全マッチングへの分解が得られました。

\(N\) が奇数の場合、(1),(3) の辺はそれぞれ \(N\) 個の \(\frac{N-1}{2}\) 組のマッチングと孤立点の組に分解することができます。とくに、孤立点は互いに相異なるように分解できます。残りの(2)の辺についても正則二部グラフは完全マッチングに分解できるため、 \(N-2\) 個の完全マッチングに分解することができます。この \(N-2\) 個の完全マッチングから適当に \(1\) つ選びます。マッチングが \((u_1,v_1), (u_2,v_2), \dots, (u_N,v_N)\) と表せるとき、各 \(i\) について上側で \(u_i\) が孤立するような最大マッチングと下側で \(v_i\) が孤立するような最大マッチングと辺 \((u_i,v_i)\) を組み合わせることで \(N\) 個の辺素な完全マッチングを得ることができます。以上により \(N+(N-2-1)=2N-3\) 個の辺素な完全マッチングへの分解が得られました。

以上より補グラフの各サイクルが偶数長の場合、 \(2N-3\) 個の完全マッチングへの分解が得られます。

サイクル長として奇数があり得る場合もほぼ同様の手順で得られます。奇数長サイクルの個数は偶数であり、 \(2k\) としたとき、サイクルをW字型に分けると、以下のような条件を満たすように \(N+N\) 頂点に分けることができます。

• 左側 \(N\) 頂点を結ぶ辺のうち、存在しない辺は \((lu_1,lv_1), (lu_2,lv_2), \dots, (lu_k,lv_k)\) のちょうど \(k\) 本で、互いに頂点を共有しない
  
• 右側 \(N\) 頂点を結ぶ辺のうち、存在しない辺は \((ru_1,rv_1), (ru_2,rv_2), \dots, (ru_k,rv_k)\) のちょうど \(k\) 本で、互いに頂点を共有しない

ここで 辺 \((lu_i, ru_i), (lv_i, rv_i)\) は必ず存在することに注意します。この辺を取り除いて代わりに \((lu_i,lv_i), (ru_i,rv_i)\) を追加したグラフを考え、上記の手順で完全マッチングへの分解を得ます。左側・右側の完全グラフの分解の仕方に注意すると 、辺 \((lu_i,lv_i), (ru_i,rv_i)\) をすべて含むような完全マッチングが存在するような分解が得られるので、この \(2k\) 本の辺を \((ru_i,lu_i), (rv_i,lv_i)\) と取り換えることで元のグラフの完全マッチングへの分解が得られます。

実際に完全マッチングへの分解を得る際のボトルネックは正則二部グラフの完全マッチングへの分解で、通常の二部マッチングアルゴリズムを \(O(N)\) 回用いることで \(O(N^{3.5})\) 時間で求めることができます。

頂点数が奇数の場合

各色の辺は最大で \(\frac{N-1}{2}\) 辺であることを踏まえると、色は \(N-2\) 色以上必要になり、これは達成できます。 構築の際はまず辺を持たない \(2\) 頂点 \(u,v\) を選んで、新たな頂点 \(x\) を用意し、

1. \(u,v\) 間に辺を追加する
2. \(N\) 頂点から \(u,v\) を除いた \(N-2\) 頂点と \(x\) を結ぶ辺を追加する

ことで \(N+1\) 頂点で次数が \(N-2\) の正則グラフが得られるので、上記の方法で \(N-2\) 色で彩色し、追加した頂点、辺を取り除くことで構築できます。