正則グラフ
概要
正則グラフ（regular graph）とは、すべての頂点の次数が等しいグラフのことで、次数が $k$ のものを $k$-正則グラフという。$n$ 頂点の $k$-正則グラフは、$k\le n-1$ かつ $nk$ が偶数のときに限って存在し、巡回グラフとして作れる。$k\ge1$ の正則二部グラフの辺は $k$ 個の完全マッチングに分かれるが、二部でない立方グラフには完全マッチングをもたないものもある。隣接行列ではすべての成分が $1$ のベクトルが固有ベクトルになり、正則であることは最大固有値が平均次数に等しいことと同値で、最小固有値 $\lambda_n$ から独立数の上界 $n(-\lambda_n)/(k-\lambda_n)$（Hoffman の比の上界）が得られ、Petersen グラフでは等号が成り立つ。
グラフのどの頂点からも同じ本数の辺が出ているとき、そのグラフを 正則グラフ という。完全グラフ、閉路、立方体の辺の網目、Petersen グラフなど、よく知られたグラフの多くは正則である。正則性は「どの頂点も同じ本数の辺をもつ」という局所的な条件にすぎないが、その帰結は大きい。頂点の個数と次数の積は偶数でなければならず、逆にこの条件と、次数が頂点の個数より小さいことさえ満たせば、正則グラフは必ず作れる。二部グラフなら辺がいくつかの完全マッチングにきれいに分かれる。隣接行列では、すべての成分が $1$ のベクトルが固有ベクトルになり、固有値の情報から独立集合の大きさまで押さえられる。
この記事では、正則グラフの定義と例を述べたあと、次を証明する。$n$ 頂点の $k$-正則グラフが存在するための条件（thm-reg-existence）、正則二部グラフの辺の完全マッチングへの分解（cor-reg-one-factorization）、三角形のない正則グラフの頂点の個数の下界（thm-reg-triangle-free）、隣接行列の固有値による正則性の判定（prop-reg-spectral）、固有値による独立集合の大きさの上界（thm-reg-hoffman）。
定義
この記事の「グラフ」は、グラフ の記事の単純無向グラフ $G=(V,E)$ で、特に断らない限り頂点の集合は空でない有限集合とする。頂点 $v$ の次数 $\deg v$ は $v$ に隣接する頂点の個数であり、$v$ に隣接する頂点の集合を $N(v)$ と書く。
$k$ を $0$ 以上の整数とする。グラフ $G=(V,E)$ のすべての頂点 $v$ について
$$
\deg v=k
$$
が成り立つとき、$G$ を $k$-正則グラフ（$k$-regular graph）という。ある $k$ について $k$-正則であるグラフを 正則グラフ（regular graph）といい、$k$ をその 次数 という。$3$-正則グラフを 立方グラフ（cubic graph）ともいう。
これは 次数(グラフ) の記事の定義「正則グラフの定義」と同じで（BM76 §1.5、p. 11 も同じ定義を置く）、最小次数と最大次数が等しいことと言い換えられる。いくつかの注意を述べる。
- $0$-正則グラフは辺をもたないグラフである。完全グラフ $K_n$ は $(n-1)$-正則である。
- 正則グラフの各連結成分は正則で、次数は全体と同じである。逆に、同じ次数の正則グラフの非交和は正則である。したがって正則であることは連結性を含まない。
- 平行辺やループを許す多重グラフでも、ループを次数 $2$ と数える約束のもとで同じように正則性を定める。この記事では扱わない。
- 頂点が無限個のグラフでも定義は意味をもつ。整数全体を頂点とし $i$ と $i+1$ を結んだグラフは $2$-正則である。以下の定理はすべて有限グラフについてのものである。
直感
正則グラフは「どの頂点に立っても、出口の数だけは同じに見える」グラフである。これは頂点どうしを入れ替える対称性よりずっと弱い。三角形と四角形を並べたグラフ $C_3\sqcup C_4$ はどの頂点の次数も $2$ だが、三角形の頂点と四角形の頂点は立場が違う。それでも次数が一様であることから、数え上げの議論が両側からそろい、行列で見たときには「すべての成分が $1$ のベクトル」という特別な固有ベクトルが手に入る。この記事の証明は、ほとんどがこの 2 つの事実から出発する。
例
- 完全グラフ $K_n$ は $(n-1)$-正則である。
- 閉路グラフ $C_n$（$n\ge3$）は $2$-正則である。
- 完全二部グラフ $K_{r,s}$ では、一方の部集合の頂点の次数は $s$、他方は $r$ なので、$K_{r,s}$ が正則であることと $r=s$ は同値である。$K_{k,k}$ は $k$-正則である。
- $2m$ 個の頂点を $m$ 組の対に分け、各対を辺で結んだグラフ（$K_2$ を $m$ 個並べたもの）は $1$-正則である。
- $d$ 次元の 超立方体グラフ $Q_d$ は、長さ $d$ の $0,1$ の列 $2^d$ 個を頂点とし、ちょうど 1 か所だけ異なる 2 つの列を結んだグラフである。各頂点で書き換えられる位置は $d$ 個あるので、$Q_d$ は $d$-正則である。$Q_3$ は立方体の頂点と辺がなすグラフである。
$n\ge1$ とし、$S$ を $\mathbb{Z}/n\mathbb{Z}$ の部分集合で、$0\notin S$ かつ $-S=S$（$s\in S$ なら $-s\in S$）を満たすものとする。$\mathbb{Z}/n\mathbb{Z}$ を頂点の集合とし、$j-i\in S$ のときに $i$ と $j$ を結んだグラフを $C_n(S)$ と書き、巡回グラフ（circulant graph）という。$-S=S$ なので「$j-i\in S$」は $i,j$ について対称で、$0\notin S$ なのでループはない。頂点 $i$ の隣接頂点は $i+s$（$s\in S$）で、これらは相異なるから、$C_n(S)$ は $\lvert S\rvert$-正則である。
$C_n(\{\pm1\})$ は閉路グラフ $C_n$（$n\ge3$）、$C_n(\mathbb{Z}/n\mathbb{Z}\setminus\{0\})$ は完全グラフ $K_n$ である。$n=8$、$S=\{\pm1,4\}$ とすると、8 角形に 4 本の対角線（向かい合う頂点を結ぶ線）を加えた $3$-正則グラフになる。
有限群 $\Gamma$ と、単位元を含まず逆元をとる操作で閉じた部分集合 $S\subset\Gamma$ に対し、$\Gamma$ を頂点の集合とし、$g^{-1}h\in S$ のときに $g$ と $h$ を結んだグラフ（Cayley グラフ。連結グラフ の記事の定義「Cayley グラフの定義」）は、頂点 $g$ の隣接頂点が $gs$（$s\in S$）の $\lvert S\rvert$ 個なので $\lvert S\rvert$-正則である。巡回グラフは $\Gamma=\mathbb{Z}/n\mathbb{Z}$ の場合であり、超立方体グラフ $Q_d$ は $\Gamma=(\mathbb{Z}/2\mathbb{Z})^d$、$S$ を標準的な $d$ 個の生成元とした場合である。
$C_3\sqcup C_4$ は $2$-正則である。しかしグラフの同型は連結成分の頂点の個数を保つので、三角形の頂点を四角形の頂点へ移す自己同型はない。したがって「正則」は「どの頂点もほかのどの頂点へ自己同型で移せる」（頂点推移的）を含まない。逆に、頂点推移的なグラフは、自己同型が次数を保つので正則である。巡回グラフと Cayley グラフは、左からの掛け算 $x\mapsto gx$ が自己同型になるので頂点推移的である。
基本的な性質
$G$ を $n$ 頂点の $k$-正則グラフとする。
- $G$ の辺は $nk/2$ 本であり、特に $nk$ は偶数である。
- 補グラフ $\overline{G}$ は $(n-1-k)$-正則である。
- $k\ge1$ で $G$ が二部分割 $(X,Y)$ をもつなら、$\lvert X\rvert=\lvert Y\rvert$ である。
1 は 次数(グラフ) の記事の命題「次数の範囲」の最後の主張（握手補題 $\sum_v\deg v=2\lvert E\rvert$ を $k$-正則の場合に使ったもの）である。2 は同記事の命題「補グラフにおける次数」$\deg_{\overline{G}}v=n-1-\deg_Gv$ による。3：どの辺も $X$ の頂点をちょうど 1 つ端点にもつので、辺の本数は $X$ の頂点の次数の和 $k\lvert X\rvert$ に等しい。同様に $k\lvert Y\rvert$ にも等しい。$k\ge1$ なので $\lvert X\rvert=\lvert Y\rvert$ である。$\square$
1 から、頂点が奇数個の正則グラフの次数は偶数である。たとえば頂点 $5$ 個の立方グラフはない。次の定理は、この偶奇の条件と、単純グラフの次数が $n-1$ 以下であることのほかに制約がないことを示す。
$n\ge1$、$k\ge0$ を整数とする。$n$ 頂点の $k$-正則グラフが存在するための必要十分条件は
$$
k\le n-1\quad\text{かつ}\quad nk\text{ が偶数}
$$
であることである。
必要性．単純グラフでは頂点 $v$ は自分自身と隣接しないので $\deg v\le n-1$、よって $k\le n-1$ である。$nk$ が偶数であることは prop-reg-basic の 1 である。
十分性．$k\le n-1$ で $nk$ が偶数とする。ex-reg-circulant により、$\mathbb{Z}/n\mathbb{Z}$ の部分集合 $S$ で $0\notin S$、$-S=S$、$\lvert S\rvert=k$ となるものを作れば、巡回グラフ $C_n(S)$ が求める $k$-正則グラフになる。
(i) $k$ が偶数のとき、$k=2r$ とおき、$S:=\{\pm1,\pm2,\dots,\pm r\}$ とする。$-S=S$ は明らかである。$2r=k\le n-1$ なので $r\le(n-1)/2$ であり、$1\le i\le r$ について $i$ と $n-i$ は $1$ 以上 $n-1$ 以下の相異なる整数である（$i=n-i$ なら $n=2i\le2r\le n-1$ となり矛盾）。また $1\le i\le r$ と $1\le j\le r$ について $i\ne n-j$ である（$i+j\le2r\le n-1$ なので）。よって $\pm1,\dots,\pm r$ は $\mathbb{Z}/n\mathbb{Z}$ の $0$ でない相異なる $2r$ 個の元で、$\lvert S\rvert=k$ である。$k=0$ なら $S=\emptyset$ で、辺のないグラフになる。
(ii) $k$ が奇数のとき、$nk$ が偶数なので $n$ は偶数である。$k=2r+1$ とおき、$S:=\{\pm1,\dots,\pm r\}\cup\{n/2\}$ とする。$n/2\equiv-n/2\pmod n$ なので $-S=S$ である。$2r+1\le n-1$ から $r\le n/2-1$ であり、(i) と同じ理由で $\pm1,\dots,\pm r$ は相異なる $2r$ 個の元である。さらに $1\le i\le r$ について $i\ne n/2$ かつ $n-i\ne n/2$（$i\le n/2-1$ なので）であるから、$n/2$ はそれらと異なり、$0$ とも異なる。よって $\lvert S\rvert=2r+1=k$ である。$\square$
$n=6$、$k=3$ なら $S=\{\pm1,3\}$ で、6 角形に 3 本の長い対角線を加えたグラフになる。これは $K_{3,3}$ と同型である（偶数番目と奇数番目の頂点が部集合になる）。
次数が小さい正則グラフは形が決まる。$1$-正則グラフは、各頂点がちょうど 1 つの頂点と対になっているので、ex-reg-basic の 4 の形（$K_2$ の非交和）に限る。$2$-正則グラフは閉路グラフの非交和に限る（閉路 の記事の命題「連結で次数がすべて 2 のグラフ」）。立方グラフの形はこのようには決まらない。橋をもつもの（ex-reg-cubic-no-matching）も、三角形も長さ 4 の閉路ももたないもの（Petersen グラフ）もある。
正則二部グラフとマッチング
辺の集合 $M$ の辺どうしが端点を共有しないとき $M$ をマッチング（マッチング(グラフ理論)）といい、すべての頂点がちょうど 1 本の $M$ の辺の端点になるとき 完全マッチング という。完全マッチングの辺からなる全域部分グラフは $1$-正則である。$k\ge1$ の $k$-正則二部グラフは完全マッチングをもつ（マッチング(グラフ理論) の記事の系「正則二部グラフの完全マッチング」）。これは次のように強められる。
$k\ge1$ とし、$G$ を $k$-正則な二部グラフとする。このとき $G$ の辺の集合は、互いに交わらない $k$ 個の完全マッチングの和集合である。
共有する端点をもつ 2 辺に異なる色を塗るように辺を塗り分けるとき、必要な色の最小の個数を辺彩色数 $\chi'(G)$ という。単純グラフはループのない多重グラフなので、多重グラフ の記事の定理「König の辺彩色定理」により、二部グラフ $G$ の辺は最大次数 $k$ 個の色で塗り分けられる。各頂点 $v$ には $k$ 本の辺が接続し、それらの色は互いに異なる $k$ 色のうちの $k$ 個なので、どの色もちょうど 1 回ずつ現れる。よって各色の辺の集合は、どの頂点でもちょうど 1 本の辺をもつ、すなわち完全マッチングである。色ごとに分ければ結論を得る。$\square$
$K_{k,k}$ では、部集合の頂点を $x_0,\dots,x_{k-1}$、$y_0,\dots,y_{k-1}$ とし、$x_i$ と $y_{i+c}$（添字は $k$ を法とする）を結ぶ辺の集合を $M_c$ とすれば、$M_0,\dots,M_{k-1}$ が分解を与える。偶数の次数については、二部グラフでなくても、$2k$-正則グラフの辺は $k$ 個の $2$-正則な全域部分グラフに分かれる（多重グラフ の記事の定理「Petersen の 2-因子定理」）。
二部でない正則グラフは完全マッチングをもつとは限らない。頂点が奇数個なら明らかにもたないが、頂点が偶数個でももたない例がある。
$K_4$ の頂点を $a,b,x,y$ とし、辺 $ab$ を除いて、代わりに新しい頂点 $w$ と辺 $wa$、$wb$ を加えたグラフを $B$ とする。$B$ は 5 頂点で、$w$ の次数は $2$、ほかの 4 頂点の次数は $3$ である。$B$ を 3 つ用意し、新しい頂点 $c$ を 3 つの $w$ と結ぶと、16 頂点の立方グラフ $G$ ができる（辺 $cw$ はどれも橋である）。
$G$ は完全マッチングをもたない。完全マッチング $M$ があったとする。各 $B$ の頂点は 5 個で奇数なので、$B$ の中の辺だけでは $B$ の頂点を覆えず、$B$ の頂点で $B$ の外の頂点と $M$ の辺で結ばれるものがある。$B$ から外へ出る辺は $wc$ だけなので、3 つの $B$ のそれぞれについて辺 $wc$ が $M$ に入る。すると $c$ が $M$ の 3 本の辺の端点になり、マッチングであることに反する。
橋をもたない立方グラフは完全マッチングをもつことが知られている（Petersen の定理。BM76 Corollary 5.4、p. 79。証明には Tutte の定理を使う）。上の例はこの定理の仮定「橋をもたない」が外せないことを示している（同書 p. 79 も、橋をもつ立方グラフは完全マッチングをもつとは限らないと注意している）。
短い閉路と頂点の個数
グラフの閉路の長さの最小値を 内周（girth）という（閉路 の記事の定義「閉路・内周・森」）。内周が大きい、すなわち短い閉路がない正則グラフは、1 つの頂点のまわりが木のように広がるので、頂点がたくさん要る。内周 $5$ 以上の場合は 閉路 の記事の定理「内周 5 以上のグラフの頂点の個数」が、最小次数 $d$ について頂点が $1+d^2$ 個以上であることを示している。ここでは内周 $4$ 以上、すなわち三角形がない場合を扱う。
$k\ge1$ とし、$G$ を三角形（長さ $3$ の閉路）をもたない $n$ 頂点の $k$-正則グラフとする。このとき $n\ge2k$ である。さらに $n=2k$ であることと、$G$ が完全二部グラフ $K_{k,k}$ と同型であることは同値である。
$k\ge1$ なので辺 $uv$ がある。$N(u)$ と $N(v)$ は交わらない。共通の元 $w$ があれば $u,v,w$ は互いに隣接し、三角形になるからである。$\lvert N(u)\rvert=\lvert N(v)\rvert=k$ なので、$n\ge\lvert N(u)\rvert+\lvert N(v)\rvert=2k$ である。
$n=2k$ とする。このとき $V=N(u)\sqcup N(v)$ である。$N(u)$ の 2 頂点 $x,x'$ が隣接したとすると、$u,x,x'$ が三角形になるので、$N(u)$ のどの 2 頂点も隣接しない。同様に $N(v)$ のどの 2 頂点も隣接しない。よって $G$ のすべての辺は $N(u)$ と $N(v)$ を結ぶ。$x\in N(u)$ の $k$ 個の隣接頂点はすべて $N(v)$ に属し、$\lvert N(v)\rvert=k$ なので、$x$ は $N(v)$ のすべての頂点と隣接する。したがって $G$ は部集合 $N(u)$、$N(v)$ の完全二部グラフで、$K_{k,k}$ と同型である。
逆に $K_{k,k}$ は $2k$ 頂点の $k$-正則グラフで、二部グラフなので奇数の長さの閉路、特に三角形をもたない（二部グラフ の記事の定理「閉路の長さによる特徴付け」）。$\square$
内周がちょうど $4$ の場合は BM76 Exercise 1.7.4 (a)（p. 15）にある。$K_{k,k}$ は内周が $4$（$k\ge2$ のとき）で、上の下界を実現する。内周 $5$ 以上の立方グラフでは $1+3^2=10$ 頂点が下界で、Petersen グラフがこれを実現する。$K_4$（内周 $3$、4 頂点）や $Q_3$（内周 $4$、8 頂点）のように、短い閉路を許せば頂点はずっと少なくてすむ。
隣接行列の固有値
頂点を $v_1,\dots,v_n$ と並べ、$G$ の隣接行列 $A$（$v_i$ と $v_j$ が隣接するとき $(i,j)$ 成分が $1$、それ以外は $0$）を考える。$A$ は実対称行列なので固有値はすべて実数で、大きい順に $\lambda_1\ge\lambda_2\ge\dots\ge\lambda_n$ と書く。すべての成分が $1$ のベクトルを $\mathbf{1}$ と書く。$A\mathbf{1}$ の第 $i$ 成分は $v_i$ の次数である。
この節では 隣接行列 の記事の補題「Rayleigh 商による最大固有値」を使う。すなわち、任意の $x\in\mathbb{R}^n$ について
$$
\lambda_n\,x^{\mathsf T}x\le x^{\mathsf T}Ax\le\lambda_1\,x^{\mathsf T}x
$$
であり、右の等号は $Ax=\lambda_1x$ のときに限って成り立つ。左の等号も $Ax=\lambda_nx$ のときに限って成り立つ（$A$ の固有ベクトルからなる正規直交基底で $x=\sum_ic_iu_i$ と書くと $x^{\mathsf T}Ax-\lambda_nx^{\mathsf T}x=\sum_i(\lambda_i-\lambda_n)c_i^2$ であり、これが $0$ になるのは $\lambda_i>\lambda_n$ となる $i$ で $c_i=0$ のとき、すなわち $x$ が固有値 $\lambda_n$ の固有空間に属するときである）。
$G$ を $n$ 頂点のグラフとし、平均次数を $\overline{d}=2\lvert E\rvert/n$ とする。次は同値である。
- $G$ は正則である。
- $\mathbf{1}$ は $A$ の固有ベクトルである。
- $\lambda_1=\overline{d}$ である。
このとき $\lambda_1$ は $G$ の次数に等しい。
1 ⇒ 2：$G$ が $k$-正則なら $A\mathbf{1}=k\mathbf{1}$ である。
2 ⇒ 1：$A\mathbf{1}=c\mathbf{1}$ なら、$A\mathbf{1}$ の第 $i$ 成分が $\deg v_i$ なので、すべての頂点の次数が $c$ である。
1 ⇒ 3：$G$ が $k$-正則なら $\overline{d}=k$ である。隣接行列 の記事の定理「最大固有値と次数」の 1 により $\overline{d}\le\lambda_1\le\Delta$（$\Delta$ は最大次数）であり、$\Delta=k$ なので $\lambda_1=k=\overline{d}$ である。
3 ⇒ 2：$\mathbf{1}^{\mathsf T}A\mathbf{1}=\sum_i\deg v_i=2\lvert E\rvert=n\overline{d}$、$\mathbf{1}^{\mathsf T}\mathbf{1}=n$ なので、$\lambda_1=\overline{d}$ は $\mathbf{1}^{\mathsf T}A\mathbf{1}=\lambda_1\mathbf{1}^{\mathsf T}\mathbf{1}$ を意味する。Rayleigh 商の補題の右の等号条件から $A\mathbf{1}=\lambda_1\mathbf{1}$ である。
最後の主張は 1 ⇒ 3 の証明の中で示した。$\square$
正則でないグラフでは $\overline{d}<\lambda_1$ である。連結グラフについての同じ判定は BH11 Proposition 3.1.2（p. 33）にある。たとえば星グラフ $K_{1,3}$ では $\overline{d}=3/2$、$\lambda_1=\sqrt3$ である。$k$-正則グラフの固有値については、ほかに次のことが知られている。
- 固有値 $k$ の重複度は連結成分の個数に等しく、すべての固有値の絶対値は $k$ 以下である（隣接行列 の記事の定理「最大固有値と次数」の 2・3）。
- 連結な $k$-正則グラフについて、$-k$ が固有値であることと二部グラフであることは同値である（同記事の定理「スペクトルによる二部グラフの判定」の 1）。
- 補グラフの固有値は $n-1-k$ と $-1-\lambda_i$（$i\ge2$）である（補グラフ の記事の定理「正則グラフの補グラフの固有値」）。
- Laplace行列 $L$ は $L=kI-A$ なので、その固有値は $k-\lambda_i$ である。正則グラフでは隣接行列と Laplace 行列が同じ情報をもつ。
独立集合の大きさの上界
どの 2 頂点も隣接しない頂点の集合を 独立集合 といい、その元の個数の最大値を 独立数 $\alpha(G)$ という。独立数を求めるのは一般に難しいが、正則グラフでは最小の固有値 $\lambda_n$ から上界が得られる。
$k\ge1$ なら $\lambda_n<0$ である。実際、$A$ の対角成分はすべて $0$ なので固有値の和 $\operatorname{tr}A$ は $0$ であり、$A\ne O$ なので $0$ でない固有値があるから、負の固有値がある。
$k\ge1$ とし、$G$ を $n$ 頂点の $k$-正則グラフ、$\lambda_n$ をその隣接行列の最小の固有値とする。このとき
$$
\alpha(G)\le\frac{n\,(-\lambda_n)}{k-\lambda_n}
$$
である。さらに、独立集合 $S$ の元の個数がこの右辺に等しければ、$S$ に属さないどの頂点も、$S$ のちょうど $-\lambda_n$ 個の頂点と隣接する。
$S$ を独立集合とし、$s:=\lvert S\rvert$ とおく。$s=0$ なら示すことはないので $s\ge1$ とする。$S$ の頂点で $1$、それ以外で $0$ をとるベクトルを $\chi$ とし、
$$
x:=\chi-\frac sn\mathbf{1}
$$
とおく。次の 3 つの値を計算する。
- $\chi^{\mathsf T}A\chi$ は $S$ の中の辺の本数の 2 倍で、$S$ は独立集合なので $0$ である。
- $A$ は対称で $A\mathbf{1}=k\mathbf{1}$ なので、$\mathbf{1}^{\mathsf T}A\chi=(A\mathbf{1})^{\mathsf T}\chi=k\,\mathbf{1}^{\mathsf T}\chi=ks$ である。
- $\mathbf{1}^{\mathsf T}A\mathbf{1}=kn$ である。
よって
$$ x^{\mathsf T}Ax=0-2\cdot\frac sn\cdot ks+\frac{s^2}{n^2}\cdot kn=-\frac{ks^2}{n},\qquad x^{\mathsf T}x=s-2\cdot\frac sn\cdot s+\frac{s^2}{n^2}\cdot n=\frac{s(n-s)}{n} $$
である。Rayleigh 商の補題の左の不等式 $\lambda_n\,x^{\mathsf T}x\le x^{\mathsf T}Ax$ に代入すると
$$ \lambda_n\,\frac{s(n-s)}{n}\le-\frac{ks^2}{n} $$
であり、両辺を $s/n>0$ で割って $\lambda_n(n-s)\le-ks$、すなわち $s(k-\lambda_n)\le n(-\lambda_n)$ を得る。$k-\lambda_n>0$ なので $s\le n(-\lambda_n)/(k-\lambda_n)$ であり、$S$ は任意の独立集合だから上界が示された。
等号の場合：$s=n(-\lambda_n)/(k-\lambda_n)$ なら上の不等式はすべて等号で、$\lambda_n\,x^{\mathsf T}x=x^{\mathsf T}Ax$ である。左の等号条件から $Ax=\lambda_nx$ である。$S$ に属さない頂点 $v$ について両辺の $v$ 成分を比べる。$A\chi$ の $v$ 成分は $v$ の $S$ の中の隣接頂点の個数 $m_v$、$A\mathbf{1}$ の $v$ 成分は $k$、$x$ の $v$ 成分は $-s/n$ なので
$$ m_v-\frac{ks}{n}=-\lambda_n\cdot\frac sn $$
すなわち $m_v=(k-\lambda_n)s/n=-\lambda_n$ である。$\square$
この上界は Hoffman によるもので、BH11 Theorem 3.5.2（p. 39）にある。同書は固有値の交錯（interlacing）を使って示しているが、上の証明はベクトル $x$ を 1 つ選んで Rayleigh 商の不等式に代入するだけで済ませている。正則性は $A\mathbf{1}=k\mathbf{1}$ として、$\mathbf{1}^{\mathsf T}A\chi$ の計算でだけ使われる。
- Petersen グラフ：$n=10$、$k=3$、$\lambda_n=-2$ なので上界は $10\cdot2/5=4$ である。$\{12,13,14,15\}$（$1$ を含む 2 元部分集合 4 個）はどの 2 つも交わるので独立集合であり、$\alpha=4$ で上界に一致する。残りの 6 頂点 $\{a,b\}$（$1\notin\{a,b\}$）はどれも $\{1,c\}$（$c\notin\{a,b\}$、$c\ne1$）の $2$ 個と隣接し、定理の等号の場合の主張（$-\lambda_n=2$）と合う。
- $K_{k,k}$：$n=2k$、$\lambda_n=-k$ なので上界は $2k\cdot k/(2k)=k$ で、部集合が実現する。
- 完全グラフ $K_n$（$n\ge2$）：$\lambda_n=-1$ なので上界は $n/(n-1+1)=1$ で、$\alpha=1$ に一致する。
- 5 角形 $C_5$：$\lambda_n=2\cos(4\pi/5)=-(1+\sqrt5)/2$ なので上界は $\sqrt5\approx2.236$ で、$\alpha(C_5)=2$ である。上界は整数とは限らず、等号が成り立つとも限らない。
条件を外した反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-reg-existence の「$nk$ が偶数」 | $n=5$、$k=3$ | $k\le n-1$ を満たすが、5 頂点の立方グラフはない |
| cor-reg-one-factorization の二部性 | ex-reg-cubic-no-matching の 16 頂点の立方グラフ | 完全マッチングをもつ（したがって完全マッチングに分かれる） |
| thm-reg-triangle-free の「三角形がない」 | $K_4$（$k=3$） | 頂点が $2k=6$ 個以上 |
| prop-reg-spectral の正則性 | 星グラフ $K_{1,3}$ | $\lambda_1=\overline{d}$（実際は $\sqrt3>3/2$） |
| thm-reg-hoffman の正則性（$k$ を $\lambda_1$ に替える） | 星グラフ $K_{1,3}$ | $\alpha\le n(-\lambda_n)/(\lambda_1-\lambda_n)$ |
1 行目：prop-reg-basic の 1 により $nk=15$ が奇数なのでない。2 行目：ex-reg-cubic-no-matching で示した。このグラフは立方グラフなので次数の条件はすべて満たし、二部性だけを欠く（三角形 $axy$ をもつ）。3 行目：$K_4$ は 4 頂点の $3$-正則グラフで、三角形をもつ。4・5 行目：$K_{1,3}$ の隣接行列の固有値は $\sqrt3,0,0,-\sqrt3$ である（$A^2$ は中心の成分 $3$ と、葉 3 つの間がすべて $1$ の $3\times3$ 行列とに分かれ、固有値は $3,3,0,0$ になり、二部グラフなのでスペクトルが $0$ について対称）。右辺は $4\sqrt3/(2\sqrt3)=2$ だが、3 枚の葉は独立集合なので $\alpha=3$ である。
補足
正則性は「各頂点の隣接頂点の個数が一定」という条件である。これを強めて、隣接する 2 頂点の共通の隣接頂点の個数も、隣接しない 2 頂点の共通の隣接頂点の個数も一定であることを要求したものが強正則グラフであり、さらに「距離 $i$ にある 2 頂点について、距離 $j$ の頂点の個数が一定」を要求したものが距離正則グラフである。Petersen グラフはどちらでもある。強正則グラフでは固有値が 3 個以下に限られ、thm-reg-triangle-free や 閉路 の記事の定理「内周 5 以上のグラフの頂点の個数」の等号の場合が現れる。
「正則」の語は、正則行列・正則関数・正則空間など分野ごとに別の意味で使われる。グラフの「正則」は次数の一様性だけを指す。$k$-正則グラフを「$k$ 価グラフ」「次数 $k$ の正則グラフ」と呼ぶこともある。完全マッチングを「$1$-因子」、$k$-正則な全域部分グラフを「$k$-因子」と呼ぶ流儀では、cor-reg-one-factorization は「正則二部グラフは $1$-因子分解をもつ」と述べられる（$k$-因子の定義は BM76 Exercise 5.1.5、p. 71、正則二部グラフの $1$-因子分解は同書 §5.2 の演習、p. 75）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
