自己補グラフ

1：相異なる $u,v$ について、$uv\in E\iff\pi(u)\pi(v)\in E$ は、両辺を否定した $uv\in[V]^2\setminus E\iff\pi(u)\pi(v)\in[V]^2\setminus E$ と同値である（$\pi$ は単射なので $\pi(u)\neq\pi(v)$）。後者は $\pi$ が $\overline G$ の自己同型であることにほかならない。
2：相異なる $u,v$ について、$uv\in E\iff\tau(u)\tau(v)\notin E\iff\sigma(\tau(u))\sigma(\tau(v))\in E$ である。2 番目の同値は、$\sigma$ の条件を $\tau(u),\tau(v)$ に使ったものの否定である。
3：$\pi\in\operatorname{Aut}G$ なら、$uv\in E\iff\pi(u)\pi(v)\in E\iff\sigma(\pi(u))\sigma(\pi(v))\notin E$ なので $\sigma\circ\pi$ は反同型である。逆に $\tau$ を反同型とすると、$\sigma^{-1}$ は $\overline G$ から $G$ への同型なので $G$ の反同型でもあり（$uv\in E\iff\sigma^{-1}(u)\sigma^{-1}(v)\notin E$ は $\sigma$ の条件を $\sigma^{-1}(u),\sigma^{-1}(v)$ に使ったものである）、2 により $\pi:=\sigma^{-1}\circ\tau\in\operatorname{Aut}G$、$\tau=\sigma\circ\pi$ となる。$\square$

$j$ についての帰納法による。$j=0$ では明らかである。$j$ で成り立つとすると、$\sigma^{j+1}(u)\sigma^{j+1}(v)$ が辺であるかどうかは、反同型の条件を $\sigma^j(u),\sigma^j(v)$（相異なる）に使うと $\sigma^j(u)\sigma^j(v)$ の逆になり、帰納法の仮定と合わせて $j+1$ の場合を得る。$j$ が奇数で $\{\sigma^j(u),\sigma^j(v)\}=\{u,v\}$ なら、$uv\in E\iff uv\notin E$ となり矛盾する。$\square$

$O$ を長さ $\ell$ の軌道とし、$v\in O$ とする。$O=\{v,\sigma(v),\dots,\sigma^{\ell-1}(v)\}$ の元は相異なり、$\sigma^\ell$ は $O$ の各元を固定する。
(a) $\ell$ が $3$ 以上の奇数とする。$v\neq\sigma(v)$ であり、$\sigma^\ell$ は $\{v,\sigma(v)\}$ を固定する。$\ell$ は奇数なので lem-scg-powers に反する。
(b) $\ell\equiv2\pmod4$ とし、$h:=\ell/2$ とおくと $h$ は奇数である。$0< h<\ell$ なので $w:=\sigma^h(v)\neq v$ であり、$\sigma^h(w)=\sigma^{\ell}(v)=v$ だから $\sigma^h$ は $\{v,w\}$ を固定する。これも lem-scg-powers に反する。
(c) 相異なる 2 個の固定点 $u,w$ があれば、$\sigma=\sigma^1$ が $\{u,w\}$ を固定し、lem-scg-powers に反する。
(a)(b) により、長さ $\ell\ge2$ の巡回では $\ell$ は偶数で $\ell\not\equiv2\pmod4$、すなわち $4$ の倍数である。(c) により長さ $1$ の巡回は高々 1 個である。$\square$

自己補グラフの反同型 $\sigma$ をとる。$n$ は $\sigma$ の巡回の長さの総和であり、thm-scg-cycles によりそれは $4$ の倍数の和に高々 1 個の $1$ を加えたものである。$\square$

$u\neq v$ とする。$\sigma(v)=v$ なので、反同型の条件は $uv\in E\iff\sigma(u)v\notin E$ となる。すなわち $u\in N(v)$ と $\sigma(u)\notin N(v)$ は同値である。$\sigma$ は $V\setminus\{v\}$ の全単射なので、$\sigma$ は $N(v)$ を $V\setminus(N(v)\cup\{v\})$ の中へ、$V\setminus(N(v)\cup\{v\})$ を $N(v)$ の中へ写し、どちらも単射である。有限集合の間に互いの中への単射があるので両者の元の個数は等しく、$\sigma|_{N(v)}$ は全単射である。よって $\deg_G(v)=\lvert N(v)\rvert=n-1-\deg_G(v)$、すなわち $\deg_G(v)=(n-1)/2$ であり、$n$ は奇数である。$\square$

$n=4k$ または $n=4k+1$（$k\ge0$）と書く。4 つの記号 $a,b,c,d$ を用意し、頂点集合を
$$V:=\{x_i\mid x\in\{a,b,c,d\},\ 1\le i\le k\}\quad(n=4k),\qquad V:=\{x_i\}\cup\{z\}\quad(n=4k+1)$$
とする。$P:=\{\{a,b\},\{b,c\},\{c,d\}\}$（道 $P_4$ の辺）とおき、辺集合 $E$ を次の 3 種類の辺の全体とする。

• 相異なる記号 $x,y$ で $\{x,y\}\in P$ となるものと、任意の $i,j$ について $x_iy_j$。
• 記号 $x\in\{b,c\}$ と、$i\neq j$ について $x_ix_j$。
• （$n=4k+1$ のとき）$x\in\{a,d\}$ と任意の $i$ について $zx_i$。
  記号の置換 $s\colon a\mapsto b\mapsto d\mapsto c\mapsto a$ は ex-scg-p4 の反同型である。$\sigma(x_i):=s(x)_i$、$\sigma(z):=z$ と定めると $\sigma$ は $V$ の全単射である。$\sigma$ が反同型であることを、相異なる 2 頂点の組の種類ごとに確かめる。
• $\{x_i,y_j\}$、$x\neq y$：$\sigma$ で $\{s(x)_i,s(y)_j\}$ に写り、$s(x)\neq s(y)$ である。前者が辺であることは $\{x,y\}\in P$、後者が辺であることは $\{s(x),s(y)\}\in P$ と同値であり、$s$ は $P_4$ の反同型なので一方だけが成り立つ。
• $\{x_i,x_j\}$、$i\neq j$：$\{s(x)_i,s(x)_j\}$ に写る。$s$ は集合 $\{b,c\}$ を $\{d,a\}$ に、$\{a,d\}$ を $\{b,c\}$ に写すので、$x\in\{b,c\}$ と $s(x)\in\{b,c\}$ の一方だけが成り立つ。
• $\{z,x_i\}$：$\{z,s(x)_i\}$ に写る。同じ理由で $x\in\{a,d\}$ と $s(x)\in\{a,d\}$ の一方だけが成り立つ。
  よって $\sigma$ は反同型であり、$(V,E)$ は $n$ 頂点の自己補グラフである。$\square$

$\sigma$ は $[V]^2$ の置換 $\hat\sigma(\{u,w\}):=\{\sigma(u),\sigma(w)\}$ を引き起こす。$p\in[V]^2$ の $\hat\sigma$ による軌道の長さ、すなわち $\hat\sigma^L(p)=p$ となる最小の $L\ge1$ が偶数であることを示す。
$p=\{u,w\}$ とし、$L$ が奇数だと仮定する。$\hat\sigma^L(p)=p$ なので、$\sigma^L$ は $u,w$ をともに固定するか、$u$ と $w$ を入れ替える。

• ともに固定する場合：$u$ の巡回の長さは $L$ を割り切るので奇数であり、仮定から $1$ である。$w$ についても同様で、$u,w$ は相異なる 2 個の固定点になり、仮定に反する。
• 入れ替える場合：$\sigma^{2L}(u)=u$ なので $u$ と $w=\sigma^L(u)$ は同じ巡回に属し、その長さ $\ell$ は $2L$ を割り切るが、$\sigma^L(u)=w\neq u$ なので $L$ は割り切らない。$\ell\ge2$ なので仮定から $4\mid\ell$、したがって $4\mid2L$ となり、$L$ が奇数であることに反する。
  よって各軌道の長さは偶数である。各軌道 $\{p,\hat\sigma(p),\dots,\hat\sigma^{L-1}(p)\}$ から代表 $p$ を 1 つ選び、$j$ が偶数の $\hat\sigma^j(p)$（$0\le j< L$）を辺とし、奇数のものを辺としない。$E$ をこうして選んだ辺の全体とする。$0\le j< L$ について、$\hat\sigma$ は $\hat\sigma^j(p)$ を $\hat\sigma^{j+1}(p)$ に写し、$j=L-1$ のときは $\hat\sigma^{L}(p)=p$（$j=0$）に写す。$L$ は偶数なので、どの場合も $j$ と行き先の指数の偶奇は異なる。したがって $\hat\sigma$ は辺を辺でない組に、辺でない組を辺に写し、$\sigma$ は $(V,E)$ の反同型である。$\square$

仮定から $uv$ は $\overline G$ の辺である。$u,v$ 以外の頂点 $w$ は、$G$ で $u$ と $v$ の両方に隣接することはない（$w$ が共通の隣接頂点になる）ので、$\overline G$ で $u$ か $v$ に隣接する。
$\overline G$ の相異なる 2 頂点 $x,y$ をとる。$xy\notin E$ なら $\overline G$ で隣接する。$xy\in E$ とする。$x=u$ なら、$y$ は $G$ で $u$ に隣接するので $G$ で $v$ に隣接せず、$\overline G$ の道 $u,v,y$ がある。$x,y$ のどちらかが $v$ の場合も同様である。$x,y\notin\{u,v\}$ なら、$x$ と $y$ はそれぞれ $\overline G$ で $u$ か $v$ に隣接する。同じ頂点に隣接すれば長さ $2$ の道があり、そうでなければ例えば $x,u,v,y$ が $\overline G$ の長さ $3$ の道である。よって $\overline G$ の任意の 2 頂点は長さ $3$ 以下の道で結ばれる。$\square$

$G\cong\overline G$ なので、$G$ と $\overline G$ は連結性も直径も等しい。$G$ が連結でないか直径が $3$ 以上なら、長さ $2$ 以下の道で結ばれない 2 頂点があるので、lem-scg-complement-diameter により $\overline G$ は連結で直径は $3$ 以下である。したがって $G$ も連結で直径は $3$ 以下である。すなわち、いずれにせよ $G$ は連結で、直径は $3$ 以下である。直径が $1$ なら $G$ は完全グラフで、$\overline G$ は辺を持たないが、2 頂点以上なので $G$ は辺を持ち、$G\cong\overline G$ に反する。よって直径は $2$ または $3$ である。$\square$