補グラフ
概要
補グラフ（complement graph）とは、グラフ $G=(V,E)$ に対し、同じ頂点集合 $V$ の上で、$G$ で隣接しない相異なる 2 頂点を辺で結んだグラフ $\overline G=(V,[V]^2\setminus E)$ のことである。2 回とると元に戻り、隣接行列は $J-I-A$ に変わる。誘導部分グラフをとる操作と可換で、非交和を結合に写し、クリークと独立集合を入れ替えるので Ramsey の定理や彩色数に現れる。$G$ に距離 $3$ 以上の 2 頂点があれば $\overline G$ の直径は $3$ 以下、距離 $4$ 以上の 2 頂点があれば $2$ 以下である。$k$-正則グラフの補グラフの固有値は $n-1-k$ と $-1-\theta$ であり、Laplace 行列の固有値は $0$ を 1 つ除き $\mu$ から $n-\mu$ に移る。
グラフ $G$ の相異なる 2 頂点は、隣接するかしないかのどちらか一方である。この二択をすべての 2 頂点について同時に入れ替えたグラフが補グラフ $\overline G$ である。頂点は変えず、$G$ の辺を消し、$G$ で結ばれていなかった 2 頂点をすべて結ぶ。補グラフをとると、辺の多いグラフは辺の少ないグラフに、互いに隣接する頂点の集まり（クリーク）は互いに隣接しない頂点の集まり（独立集合）に変わる。そのため、ある問題を補グラフの問題に言い換えると見通しがよくなることが多い。この記事では、補グラフと部分グラフ・非交和・結合との関係、直径についての定理、隣接行列と Laplace 行列の固有値の移り方を示す。
定義
この記事のグラフは、グラフ の記事の定義「グラフの定義」の意味の単純無向グラフ $G=(V,E)$（$E\subset[V]^2$、$[V]^2$ は $V$ の相異なる 2 元からなる部分集合全体）である。辺数・次数・行列を扱うところでは有限グラフを考え、頂点数を $n$ と書く。
グラフ $G=(V,E)$ の補グラフ（complement graph, complement）とは、同じ頂点集合 $V$ と辺集合 $[V]^2\setminus E$ からなるグラフ
$$\overline G:=\bigl(V,\ [V]^2\setminus E\bigr)$$
のことをいう。すなわち、相異なる $u,v\in V$ について $uv\in E(\overline G)\iff uv\notin E(G)$ である。$G^c$ とも書く。
これは グラフ の記事の定義「補グラフとグラフの和」と同じである。補集合をとる基準は、同じ頂点集合の上の可能な辺全体 $[V]^2$ である。補グラフは頂点を増やしも減らしもしない。平行辺やループを許す多重グラフでは「隣接するか否か」が二択でないので、この形の補グラフはない。
補グラフとともに次の 2 つの演算を使う（グラフ の記事の定義「補グラフとグラフの和」）。頂点集合が交わらないグラフ $G,H$ について、$G\cup H:=(V(G)\cup V(H),\ E(G)\cup E(H))$ を非交和、これに $V(G)$ の各頂点と $V(H)$ の各頂点を結ぶ辺をすべて加えたグラフを結合（join）といい $G+H$ と書く。$n$ 頂点の完全グラフを $K_n$、その補グラフ（辺のない $n$ 頂点のグラフ）を $E_n$ と書く。
直感
補グラフは、隣接の有無の表を白黒反転したものである。頂点を人、辺を「知り合い」とすれば、補グラフの辺は「知り合いでない」である。反転は 2 頂点ごとの局所的な操作なので、クリーク（全員が知り合い）と独立集合（全員が知り合いでない）のように 2 頂点ごとの条件で決まる性質はそのまま入れ替わる。一方、連結性や直径のように道をたどって決まる大域的な性質は、単純には反転しない。それでも「$G$ で遠く離れた 2 頂点がある」ことは $\overline G$ を強く縛る。$G$ で離れた 2 頂点 $u,v$ は $\overline G$ で隣接し、ほかのどの頂点も $\overline G$ で $u$ か $v$ に隣接するので、$\overline G$ ではどの 2 頂点も近くなる。
例
$\overline{K_n}=E_n$、$\overline{E_n}=K_n$ である。部集合の大きさが $m,n$ の完全二部グラフ $K_{m,n}$ は、辺のないグラフ 2 つの結合 $E_m+E_n$ である。後の prop-cg-union-join により、その補グラフは $\overline{E_m}\cup\overline{E_n}=K_m\cup K_n$、すなわち完全グラフ 2 つの非交和である。
頂点 $1,2,3,4$ と辺 $12,23,34$ の道 $P_4$ の補グラフの辺は $13,14,24$ で、これは道 $3,1,4,2$ である。よって $\overline{P_4}\cong P_4$ であり、$P_4$ は自己補グラフである（5 角形 $C_5$ も自己補グラフである）。
頂点 $0,1,\dots,5$ と辺 $\{i,i+1\}$（添字は $6$ を法とする）の閉路 $C_6$ の補グラフでは、$i$ は $i\pm2$ と $i+3$ に隣接する。$\{0,2,4\}$ と $\{1,3,5\}$ はそれぞれ三角形をなし、残りの辺 $03,14,25$ は 2 つの三角形を 1 本ずつ結ぶ。よって $\overline{C_6}$ は三角柱の辺からなるグラフである。
定理の仮定を外した反例は、性質の節の最後に表にまとめる。
性質
基本的な性質
グラフ $G=(V,E)$ について次が成り立つ。
- $\overline{\overline G}=G$ である。
- $G$ が $n$ 頂点・$m$ 辺の有限グラフなら、$\overline G$ の辺は $\binom n2-m$ 本で、各頂点 $v$ で $\deg_{\overline G}(v)=n-1-\deg_G(v)$ である。
- $V=\{v_1,\dots,v_n\}$ と番号をつけ、$G$ の隣接行列を $A$ とすると、$\overline G$ の隣接行列は $J-I-A$ である。ここで $J$ はすべての成分が $1$ の $n$ 次正方行列、$I$ は単位行列である。
- 任意の $W\subset V$ について $\overline G[W]=\overline{G[W]}$ である。ここで $G[W]$ は $W$ の誘導部分グラフで、右辺の補グラフは $W$ の上でとる。
- 全単射 $f\colon V\to V'$ が $G$ から $G'=(V',E')$ へのグラフ同型であることと、同じ $f$ が $\overline G$ から $\overline{G'}$ への同型であることは同値である。特に $G\cong G'\iff\overline G\cong\overline{G'}$ である。
1：$[V]^2\setminus([V]^2\setminus E)=E$ である（$E\subset[V]^2$）。
2：$E$ と $E(\overline G)$ は $[V]^2$ を 2 つに分けるので、辺の本数の和は $\lvert[V]^2\rvert=\binom n2$ である。次数の式は 次数(グラフ) の記事の命題「補グラフにおける次数」である。
3：$\overline G$ の隣接行列の $(i,j)$ 成分は、$i=j$ なら $0$、$i\neq j$ なら $v_iv_j\notin E$ のとき $1$、$v_iv_j\in E$ のとき $0$、すなわち $1-a_{ij}$ である。$J-I-A$ の $(i,i)$ 成分は $1-1-0=0$、$i\neq j$ の成分は $1-a_{ij}$ なので一致する。
4：両辺の頂点集合は $W$ である。相異なる $u,v\in W$ について、$uv$ が $\overline G[W]$ の辺であることは $uv\notin E$ と同値であり、$uv$ が $\overline{G[W]}$ の辺であることは $uv\notin E\cap[W]^2$、すなわち（$u,v\in W$ なので）$uv\notin E$ と同値である。
5：$f$ が同型なら、相異なる $u,v$ について $uv\notin E\iff f(u)f(v)\notin E'$ であり、これは $f$ が $\overline G$ から $\overline{G'}$ への同型であることを意味する（グラフ の記事の命題「同型の基本性質」の 3）。逆は、この結果を $\overline G,\overline{G'}$ に使い 1 を用いればよい。$\square$
5 で $G'=G$ とすれば、$G$ の自己同型と $\overline G$ の自己同型は同じ頂点の置換であり、自己同型群は等しい（自己補グラフ の記事の命題「自己同型群と補グラフ」）。2 から、有限グラフが $k$-正則なら補グラフは $(n-1-k)$-正則である。また 1 により、補グラフをとる操作は $V$ 上のグラフ全体の全単射で、辺が $m$ 本のグラフを辺が $\binom n2-m$ 本のグラフに写す。したがって $V$ 上の $m$ 辺のグラフと $\binom n2-m$ 辺のグラフは同じ個数だけある（どちらも $\binom{\binom n2}{m}$ 個）。
頂点集合が交わらないグラフ $G,H$ について
$$\overline{G\cup H}=\overline G+\overline H,\qquad \overline{G+H}=\overline G\cup\overline H$$
である。ここで各補グラフは、それぞれのグラフ自身の頂点集合の上でとる。
$V_1:=V(G)$、$V_2:=V(H)$ とおく。$V_1\cup V_2$ の相異なる 2 頂点の組は、両方 $V_1$ にあるもの、両方 $V_2$ にあるもの、$V_1$ と $V_2$ に 1 つずつあるものに分かれる。$G\cup H$ の辺は $E(G)\cup E(H)$ で、3 番目の種類の辺はない。したがって $\overline{G\cup H}$ の辺は、1 番目の種類では $[V_1]^2\setminus E(G)=E(\overline G)$、2 番目の種類では $E(\overline H)$、3 番目の種類ではすべての組であり、これは $\overline G+\overline H$ の辺集合にほかならない。第 1 式を $\overline G,\overline H$ に使うと、prop-cg-basic の 1 により $\overline{\overline G\cup\overline H}=G+H$ となり、両辺の補グラフをとって第 2 式を得る。$\square$
頂点集合が空でないグラフ $G=(V,E)$ について、次は同値である。
- $\overline G$ は連結でない。
- $V$ を空でない 2 つの集合 $V_1,V_2$ に分けて、$V_1$ の各頂点と $V_2$ の各頂点が $G$ で隣接するようにできる。すなわち $G=G[V_1]+G[V_2]$ と結合に分解できる。
連結グラフ の記事の命題「切断による判定」により、1 は、$\emptyset\neq S\subsetneq V$ で $S$ と $V\setminus S$ を結ぶ $\overline G$ の辺がないものが存在することと同値である。$S$ の頂点と $V\setminus S$ の頂点を結ぶ $\overline G$ の辺がないことは、それらがすべて $G$ で隣接することにほかならない。$V_1=S$、$V_2=V\setminus S$ とすればよい。$\square$
例えば $K_{m,n}=E_m+E_n$（$m,n\ge1$）の補グラフは連結でなく、$P_4$ はどう 2 つに分けても結合にならない（$\overline{P_4}\cong P_4$ は連結である）。
クリーク・独立集合と彩色
頂点集合 $S$ のどの 2 頂点も隣接するとき $S$ をクリーク、どの 2 頂点も隣接しないとき独立集合という。定義から、$S$ が $G$ のクリークであることと $\overline G$ の独立集合であることは同値であり、クリークの最大の大きさ（クリーク数）$\omega$ と独立集合の最大の大きさ（独立数）$\alpha$ について $\omega(G)=\alpha(\overline G)$ である（彩色数 の記事の定義「クリーク数と独立数」の後の段落）。
この言い換えにより、Ramseyの定理 は補グラフの言葉で述べられる。完全グラフの辺を 2 色に塗ることは、一方の色の辺をグラフ $G$、他方の色の辺を $\overline G$ とみることと同じなので、Ramsey 数 $R(s,t)$ は「頂点が $R(s,t)$ 個以上のどのグラフ $G$ も、$s$ 頂点のクリークを持つか、$\overline G$ が $t$ 頂点のクリークを持つ（$G$ が $t$ 頂点の独立集合を持つ）」ような最小の数である。例えば 6 頂点のグラフでは、$G$ か $\overline G$ のどちらかが三角形を含み（Ramsey数 R(3,3)=6）、$C_5$ とその補グラフ（$C_5$ と同型）はどちらも三角形を含まないので、5 頂点では成り立たない。
彩色数 $\chi$ については、$n$ 頂点のグラフ $G$ で
$$n\le\chi(G)\,\chi(\overline G),\qquad \chi(G)+\chi(\overline G)\le n+1$$
が成り立つ（彩色数 の記事の命題「補グラフの彩色数との関係」。和の上界は Nordhaus と Gaddum による。BM76 Exercise 8.1.4 (b)、p. 121）。この 2 つを組み合わせると、和と積の残りの向きの評価が出る。
$n\ge1$ 頂点のグラフ $G$ について
$$2\sqrt n\le\chi(G)+\chi(\overline G),\qquad \chi(G)\,\chi(\overline G)\le\Bigl(\frac{n+1}{2}\Bigr)^2$$
である。
$a=\chi(G)$、$b=\chi(\overline G)$ とおく。実数について $(a+b)^2-4ab=(a-b)^2\ge0$ である。$ab\ge n$ なので $(a+b)^2\ge4ab\ge4n$、よって $a+b\ge2\sqrt n$ である。また $a+b\le n+1$ なので $ab\le\bigl(\frac{a+b}{2}\bigr)^2\le\bigl(\frac{n+1}{2}\bigr)^2$ である。$\square$
4 つの評価はどれも等号が成り立つことがある。$K_n$ では $\chi(K_n)=n$、$\chi(E_n)=1$ なので積は $n$、和は $n+1$ である。$P_4$ では $\chi(P_4)=\chi(\overline{P_4})=2$ で和は $4=2\sqrt4$、$C_5$ では $\chi(C_5)=\chi(\overline{C_5})=3$ で積は $9=\bigl(\frac{5+1}{2}\bigr)^2$ である。
直径
2 頂点 $u,v$ の距離 $d_G(u,v)$ は、$u$ と $v$ を結ぶ道の長さの最小値であり、結ぶ道がなければ $\infty$ とする（距離(グラフ)）。2 頂点以上のグラフの直径は 2 頂点の距離の最大値であり、連結でなければ $\infty$ である。$G$ で遠く離れた 2 頂点があると、$\overline G$ の直径は小さい。
$G=(V,E)$ をグラフとする。
- $d_G(u,v)\ge3$ となる 2 頂点 $u,v$ があれば、$\overline G$ は連結で、$\overline G$ の任意の 2 頂点の距離は $3$ 以下である。
- $d_G(u,v)\ge4$ となる 2 頂点 $u,v$ があれば、$\overline G$ は連結で、$\overline G$ の相異なる任意の 2 頂点は、$\overline G$ で隣接するか $\overline G$ で共通の隣接頂点をもつ。特に $\overline G$ の任意の 2 頂点の距離は $2$ 以下である。
どちらでも $d_G(u,v)=\infty$（$u,v$ が異なる連結成分にある）の場合を含む。したがって、2 頂点以上の有限グラフ $G$ の直径が $3$ 以上なら $\overline G$ の直径は $3$ 以下であり、$G$ の直径が $4$ 以上なら $\overline G$ の直径は $2$ 以下である。
1 は 自己補グラフ の記事の補題「補グラフの直径」で示されている（$d_G(u,v)\ge3$ は、$u,v$ が隣接せず共通の隣接頂点ももたないことと同じである）。2 は BM76 Exercise 1.6.12（p. 14）にある。
2 を示す。$d_G(u,v)\ge4$ とし、相異なる 2 頂点 $x,y$ をとる。$xy\notin E$ なら $x,y$ は $\overline G$ で隣接する。以下 $xy\in E$ とし、$u$ か $v$ が $\overline G$ における $x,y$ の共通の隣接頂点であることを示す。
$u$ がそうでないとする。これは、$u\in\{x,y\}$ であるか、$u$ が $G$ で $x$ または $y$ に隣接することを意味する。いずれの場合も、$d_G(u,a)\le1$ となる $a\in\{x,y\}$ がある。同様に $v$ もそうでないなら、$d_G(v,b)\le1$ となる $b\in\{x,y\}$ がある。$xy\in E$ なので $d_G(a,b)\le1$ である。グラフの距離の三角不等式（距離(グラフ) の記事の命題「距離空間の公理」）により
$$d_G(u,v)\le d_G(u,a)+d_G(a,b)+d_G(b,v)\le3$$
となり、$d_G(u,v)\ge4$ に反する。よって $u$ か $v$ は $x,y$ のどちらとも異なり、$G$ で $x$ にも $y$ にも隣接しない。すなわち $\overline G$ で $x$ と $y$ の両方に隣接する。
以上で、$\overline G$ の相異なる任意の 2 頂点は長さ $2$ 以下の道で結ばれる。$V\neq\emptyset$ なので $\overline G$ は連結である。最後の主張は、直径が $3$ 以上（または $4$ 以上）であれば、距離がその値に等しい 2 頂点をとって 1・2 を使えばよい。$\square$
$G$ が連結でないときは $d_G(u,v)=\infty\ge4$ となる $u,v$ があるので、2 から「$G$ が連結でなければ $\overline G$ は連結で直径 $2$ 以下」が従う。これは 連結グラフ の記事の定理「辺の本数・最小次数・補グラフによる十分条件」の 3 と同じ内容であり、特に $G$ と $\overline G$ の少なくとも一方は連結である。また定理から、$G$ と $\overline G$ の直径が両方とも $4$ 以上になることはなく、両方が $3$ 以上なら両方ともちょうど $3$ である。$P_4$ はその例である（$P_4$ の両端点の距離は $3$ で、$\overline{P_4}\cong P_4$）。
固有値
$n$ 頂点のグラフの隣接行列 $A$ は実対称行列なので、固有値はすべて実数で、固有ベクトルからなる $\mathbb{R}^n$ の正規直交基底がある（隣接行列 の記事の注意「実対称行列のスペクトル定理」）。すべての成分が $1$ のベクトルを $\mathbf 1$ と書く。
$G$ を $n$ 頂点の $k$-正則グラフとする。$A\mathbf 1=k\mathbf 1$ であり、$A$ の固有値を重複を込めて $k,\theta_2,\dots,\theta_n$ と並べることができる。このとき $\overline G$ の隣接行列の固有値は、重複を込めて
$$n-1-k,\quad -1-\theta_2,\quad\dots,\quad -1-\theta_n$$
である。さらに $\overline G$ の隣接行列の固有ベクトルからなる正規直交基底として、$A$ のものと同じ基底をとれる。
$A$ の各行には $1$ がちょうど $k$ 個あるので $A\mathbf 1=k\mathbf 1$ である。$W:=\{x\in\mathbb{R}^n\mid \mathbf 1^{\mathsf T}x=0\}$ とおく。$x\in W$ なら $\mathbf 1^{\mathsf T}Ax=(A\mathbf 1)^{\mathsf T}x=k\,\mathbf 1^{\mathsf T}x=0$ なので $AW\subset W$ であり、$A$ を $W$ に制限した写像は標準内積について対称である。スペクトル定理により、$W$ の正規直交基底 $u_2,\dots,u_n$ で $Au_i=\theta_iu_i$ となるものがある。$u_1:=\mathbf 1/\sqrt n$ を加えた $u_1,\dots,u_n$ は $\mathbb{R}^n$ の正規直交基底で、$Au_1=ku_1$ なので、$A$ の固有値は重複を込めて $k,\theta_2,\dots,\theta_n$ である。
prop-cg-basic の 3 により $\overline G$ の隣接行列は $\overline A=J-I-A$ である。$J=\mathbf 1\mathbf 1^{\mathsf T}$ なので $Ju_1=nu_1$、$i\ge2$ では $Ju_i=\mathbf 1(\mathbf 1^{\mathsf T}u_i)=0$ である。よって
$$\overline Au_1=(n-1-k)\,u_1,\qquad \overline Au_i=(-1-\theta_i)\,u_i\quad(i\ge2)$$
であり、$u_1,\dots,u_n$ が基底なので、これが $\overline A$ の固有値のすべてを重複を込めて与える。$\square$
正則でないグラフでは $\mathbf 1$ が $A$ の固有ベクトルとは限らず、この形の関係は成り立たない（下の反例の表）。一方、次数を対角に並べた行列を $D$ として、Laplace 行列 $L:=D-A$（BH11 §1.1、pdf p. 11）については、正則性なしに同じ形の関係が成り立つ。
$n$ 頂点のグラフ $G$ の Laplace 行列 $L$ について、$L\mathbf 1=0$ であり、$L$ の固有値を重複を込めて $0,\mu_2,\dots,\mu_n$ と並べることができる。このとき $\overline G$ の Laplace 行列は $nI-J-L$ で、その固有値は重複を込めて $0,\ n-\mu_2,\ \dots,\ n-\mu_n$ である。さらに、任意のグラフの Laplace 行列の固有値は $0$ 以上なので、$\mu_i\le n$ である。
$L$ の各行の和は次数から隣接頂点の個数を引いたもので $0$ なので $L\mathbf 1=0$ である。prop-cg-basic の 2・3 により、$\overline G$ の次数の対角行列は $(n-1)I-D$、隣接行列は $J-I-A$ なので、$\overline G$ の Laplace 行列は $(n-1)I-D-(J-I-A)=nI-J-L$ である。$L$ は対称で $L\mathbf 1=0$ だから、thm-cg-regular-spectrum の証明と同じく $u_1=\mathbf 1/\sqrt n$ と、$Lu_i=\mu_iu_i$ となる $W$ の正規直交基底 $u_2,\dots,u_n$ がとれる。すると $(nI-J-L)u_1=nu_1-nu_1-0=0$、$i\ge2$ で $(nI-J-L)u_i=(n-\mu_i)u_i$ である。
任意のグラフ $H=(V,F)$ の Laplace 行列 $L_H$ と $x\in\mathbb{R}^V$ について、各辺 $uv$ が $x_u^2+x_v^2-2x_ux_v$ を 1 回ずつ与えるので
$$x^{\mathsf T}L_Hx=\sum_{v}\deg_H(v)\,x_v^2-2\sum_{uv\in F}x_ux_v=\sum_{uv\in F}(x_u-x_v)^2\ge0$$
である。固有値 $\lambda$ の単位固有ベクトル $x$ では $x^{\mathsf T}L_Hx=\lambda$ なので $\lambda\ge0$ である。これを $H=\overline G$ に使えば $n-\mu_i\ge0$ である。$\square$
この命題は BH11 §1.3.2（pdf p. 14）にあり、正則グラフの隣接行列についての thm-cg-regular-spectrum も同じ箇所に述べられている。Laplace 行列の固有値 $0$ の重複度は連結成分の個数に等しい（BH11 Proposition 1.3.7、pdf p. 17。この記事では証明しない）ので、$\overline G$ が連結でないことは $L$ が固有値 $n$ をもつことと同値である。
- $C_6$ は 2-正則で、固有値は $2\cos(2\pi j/6)$（$j=0,\dots,5$）、すなわち $2,1,1,-1,-1,-2$ である（隣接行列 の記事の例「閉路グラフ」）。thm-cg-regular-spectrum により、補グラフ（三角柱、ex-cg-p4-c6）の固有値は $6-1-2=3$ と $-1-\theta$ で、$3,\,-2,\,-2,\,0,\,0,\,1$ である。
- Petersen グラフ（ex-cg-petersen）は 3-正則で、固有値は $3$（1 個）、$1$（5 個）、$-2$（4 個）である（隣接行列 の記事の例「Petersen グラフ」）。その補グラフである $K_5$ の線グラフ $T(5)$ は 6-正則で、固有値は $10-1-3=6$（1 個）、$-1-1=-2$（5 個）、$-1+2=1$（4 個）となり、BH11 §1.4.5（pdf p. 20）の値と一致する。
反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-cg-diameter の 1 の $d_G(u,v)\ge3$（直径 $2$ にする） | 星 $K_{1,3}$ | $\overline G$ は連結 |
| thm-cg-diameter の 2 の $d_G(u,v)\ge4$ を $\ge3$ に | 道 $P_4$ | $\overline G$ の直径は $2$ 以下 |
| thm-cg-regular-spectrum の正則性 | 星 $K_{1,3}$ | $\overline G$ の固有値は $n-1-k$ と $-1-\theta_i$ |
| cor-cg-join の 2 の「すべての組が隣接」を「辺がある」に | 道 $P_4$（$\{1,2\}$ と $\{3,4\}$） | $\overline G$ は連結でない |
- 星 $K_{1,3}$（中心 $c$ と葉 $x,y,z$）の直径は $2$ である。補グラフでは $c$ が孤立し、$x,y,z$ が三角形をなすので、$\overline{K_{1,3}}=K_3\cup K_1$ は連結でない。直径が $2$ のグラフについては、補グラフの連結性について何もいえない（$C_5$ は直径 $2$ で補グラフも連結である）。
- $P_4$ の直径は $3$ で、$\overline{P_4}\cong P_4$ の直径も $3$ である。2 の $4$ は $3$ に下げられない。
- $K_{1,3}$ の固有値は $\pm\sqrt3,0,0$ である（$A^2$ の固有値が $3,3,0,0$ で、階数 $2$）。補グラフ $K_3\cup K_1$ の固有値は $2,0,-1,-1$ である。$K_{1,3}$ は正則でないので $k$ が定まらず、どの $\theta$ についても $-1-\theta$ は $-1\mp\sqrt3$ か $-1$ で、$2$ や $0$ を与えない。
- $P_4$ の頂点を $\{1,2\}$ と $\{3,4\}$ に分けると、2 組の間に辺 $23$ はあるが、$14$ などは辺でない。補グラフ $\overline{P_4}\cong P_4$ は連結である。
補足
補グラフと同型なグラフを自己補グラフという。辺が可能な組のちょうど半分あり、頂点数は $4$ で割って $0$ か $1$ 余る。
cor-cg-join と prop-cg-union-join を繰り返し使うと、1 頂点のグラフから非交和と補グラフをとる操作だけで作れるグラフの族が得られる。この族は $P_4$ を誘導部分グラフとして含まない、頂点を 1 個以上もつグラフ全体と一致し、そのようなグラフでは 2 頂点以上なら $G$ か $\overline G$ が連結でない（誘導部分グラフ の記事）。
補グラフをとっても同じ種類にとどまるグラフの族もある。完全グラフでも辺のないグラフでもない正則グラフで、隣接する 2 頂点の共通の隣接頂点の個数と、隣接しない 2 頂点の共通の隣接頂点の個数がそれぞれ一定のものを強正則グラフという（BH11 §9.1、pdf p. 123）。強正則グラフの補グラフは再び強正則である（同書 §9.1.1、pdf p. 124）。$T(5)$ とその補グラフである Petersen グラフはその例である（同書 §1.4.5、pdf p. 20）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
