この解説はスライドで省略された内容を証明したものとなっています。スライドに一度目を通して大枠を理解してから読むことをお勧めします。

[0] 定義

\(N\) 頂点のグラフであって、頂点 \(a_i,b_i\) 間に辺を張ったグラフを \(G_P,\) 頂点 \(c_i,d_i\) 間に張ったグラフを \(G_Q\) とします。また、\(G_P\) の連結成分を \(C_1,C_2,\dots,C_{k},\) \(G_Q\) の連結成分を \(C_{k+1},C_{k+2},\dots,C_{k+k'}\) とします。

\(k+k'\) 頂点のグラフであり、各 \(i\ (1\leq i \leq M)\) について、\(G_P,C_Q\) において辺 \(i\) を含む連結成分 \(C_a,C_b\) に対し頂点 \(a,b\) 間に辺を張ったグラフを \(G_{PQ}\) とします。

\(G_{PQ}\) の連結成分ごとに考えればいいです。以下、\(G_P,C_Q\) に孤立点は存在せず、\(G_{PQ}\) は連結であるものとします。

\(G_P\) の連結成分 \(C_i\) が以下の条件のいずれかを満たすとき、\(C\) は freeな連結成分 であると書きます。\(G_Q\) の連結成分についても同様です。

• \(C_i\) の頂点数が \(2\)
• \(C_i\) に属する辺 \(j,k\) であって、\(G_P\) 内では端点をただ一つだけ共有する一方、\(G_Q\) では端点を共有しない、または多重辺になっているものが存在する。

free な連結成分では \(Q\) に影響を及ぼすことなく偶置換を施せます（これさえ成り立てばいいのでスライドでの定義に加えて「頂点数が \(2\)」の連結成分も free な連結成分として扱っています。このようにするとスライドでは厄介な例外ケースとされていたサイズが \(2\) の連結成分に関連したケースがすべて解決します）。

以下ではスライドで所略された次の \(2\) つの内容を証明します。

• \(G_{PQ}\) が free な連結成分を含み、\(G_P\) の連結成分 \(C_i\) が free な連結成分でない場合、\(C_i\) に属する辺は \(G_Q\) において同一の連結成分 \(C_j\) に含まれ、\(C_j\) は free な連結成分である。
• \(G_{PQ}\) が free な連結成分を含まない場合、 \(|G_P|,|G_Q| \leq 4\) が成り立つ。

[1] free な連結成分が存在する場合

前半の内容を証明します。

\(G_P\) の連結成分 \(C_i\) の全域木を \(1\) つ取ります。\(G_i\) が free でないという仮定から、端点を \(1\) つだけ共有する \(G_i\) の \(2\) 辺は \(G_Q\) においても端点を \(1\) つだけ共有し、同じ連結成分に属します。よって全域木の辺については、葉側から考えると \(G_Q\) においても同一の連結成分 \(C_{j}\) に属することがわかります。

\(C_i\) に属する各辺 \(e\) について、全域木の辺 \(e'\) であって、端点を \(1\) つだけ共有するものが存在します。これは、存在しないと仮定すると全域木の辺が \(e\) の多重辺のみになり、\(|C_i|=2\) となってしまうためです。よって辺 \(e\) も \(C_{j}\) に属することが言えます。

さて、

• \(C_i\) に属さない
• \(C_j\) の属する
• \(C_i,C_j\) の属する辺 \(e\) であって、端点を \(1\) つだけ共有するものが存在する

の \(3\) 条件を満たす辺が存在しない場合、\(C_i\) と \(C_j\) の辺集合は一致し、特に \(C_j\) は free な連結成分ではありません。このとき、連結グラフ \(G_{PQ}\) 内に free な連結成分が存在しなくなってしまいます。よって \(3\) 条件を満たす辺が存在し、\(C_j\) は free な連結成分であることがわかります。

[2] free な連結成分が存在しない場合

後半の内容を証明します。

\(G_P\) において頂点 \(v\) を端点とする辺のラベルの集合を \(E_P(v),\) \(G_Q\) において頂点 \(v\) を端点とする辺のラベルの集合を \(E_Q(v)\) とします。以下、 \(G_P,G_Q\) は同型でないものとし、 \(G_P\) の連結成分 \(C_1\) が free な連結成分ではないとします。定義から \(3 \leq |C_1|\) です。

まず [1] と同様の議論から \(C_1\) に属する辺は \(C_Q\) において同一の連結成分 \(C_{k+1}\) に属し、 \(G_{PQ}\) は連結であるという仮定から \(C_1,C_{k+1}\) は \(G_P,G_Q\) 全体となっています。

以下では辺 \(i,j,k\) であって、

• \(G_P\) において \(3\) 辺からなるウニ、 \(G_Q\) において三角形をなす
• \(G_P\) において \(2\) 辺サイクルに \(1\)辺追加したもの、\(G_Q\) においてパスグラフ をなす

およびこの逆のいずれかが成り立つものが存在することを示します。この構造を含む場合、連結な頂点を \(5\) つ以上に増やすことができないことが容易にわかります。

\(G_P,G_Q\) が同型でないため、\(E_P(v)=E_Q(v')\) をみたす \(v'\) が存在しないような \(v\) が取れます。

[2-1] \(G_P\) において \(v\) を端点とする \(2\) 辺であって、共有する端点が \(v\) のみである \(2\) 辺が存在しないとき

\(i \in E_P(v)\) とします。\(G_P\) における辺 \(i\) のもう一つの端点を \(v'\) とし、\(G_Q\) での辺 \(i\) の端点を \(u_1,u_2\) とします。

\(3 \leq |G_Q|\) より \(u_1\) を端点とし \(u_2\) を端点としない辺 \(j\) が取れます。辺 \(i,j\) は \(G_Q\) において端点を \(1\) つしか共有しないので \(j \notin E_P(v)\) です。また、 \(E_Q(u_2)\neq E_P(v)\) より頂点 \(u_2\) を端点とする辺 \(k\ (\notin E_P(v))\) が存在します。

\(k\) のもう \(1\) つの端点が \(u_1\) でない場合、辺 \(i,j,k\) は \(G_Q\) においてパスグラフをなします。freeな連結成分でないという仮定から、 \(G_P\) において辺 \(i,k\) は端点 \(v'\) だけ共有し、\(j,k\) は（端点 \(v'\) を共有しているので）多重辺となっています。よって辺 \(i,j,k\) は \(G_P\) において\(2\) 辺からなるサイクルに \(1\) 辺追加したグラフをなしています。以上より \(G_P,G_Q\) は上記の \(2\) 番目の構造を含みます。

\(k\) のもう \(1\) つの端点が \(u_1\) である場合、辺 \(i,j,k\) は \(G_Q\) において\(2\) 辺からなるサイクルに \(1\) 辺追加したグラフをなしています。free な連結成分でないという仮定から、\(G_P\) において辺 \(i,j\) は端点 \(v'\) だけ共有し、辺 \(j,k\) も端点 \(v''\) だけ共有します。一方辺 \(i,k\) は（ \(v\) を共有できないので）端点を \(1\) つも共有しません 。よって \(v'\neq v''\) であり、辺 \(i,j,k\) は \(G_P\) においてパスグラフをなします。以上より \(G_P,G_Q\) は上記の \(2\) 番目の構造を含みます。

[2-2] \(G_P\) において \(v\) を端点とする \(2\) 辺であって、共有する端点が \(v\) のみである \(2\) 辺 \(i,j\) が存在するとき

\(G_P\) が free でないという仮定から \(\{i,j\} \subset E_Q(u)\) である \(u\) がただ \(1\) つ存在します。同型でないという仮定から（必要であれば \(P,Q\) を入れ替えて） \(k \in E_P(v),\ k \notin E_Q(u)\) をみたす辺 \(k\) が取れます。

\(k\) が \(i,j\) いずれの多重辺でもない場合、\(i,k\) は \(G_Q\) においても端点をただ \(1\) つ共有し、それは \(u\) ではないです（ \(j,k\) についても同様）。よって辺 \(i,j,k\) は \(G_Q\) において三角形をなし、\(G_P\) ではウニグラフをなしているので、上記の \(1\) 番目の構造を含みます。

\(k\) が \(i\) の多重辺である場合、 \(i,k\) は \(G_Q\) において端点を共有しない一方、 \(j,k\) は \(u\) でない頂点をただ \(1\) つ共通の端点として持ちます。よって辺 \(i,j,k\) は \(G_Q\) においてパスグラフをなし、\(G_P\) では \(2\) 辺からなるサイクルに \(1\) 辺追加したグラフになっています。よって \(G_P,G_Q\) は上記の \(2\) 番目の構造を含みます。