線グラフ

1．$uv$ の $L(G)$ での隣接頂点は、$uv$ と異なり $u$ または $v$ を端点にもつ辺である。$u$ を端点にもち $uv$ と異なる辺は $d(u)-1$ 本、$v$ を端点にもち $uv$ と異なる辺は $d(v)-1$ 本ある。両方に属する辺は $u$ と $v$ をともに端点にもつので $uv$ 自身であり、$uv$ はどちらにも数えていない。よって 2 つの集合は交わらず、次数は $(d(u)-1)+(d(v)-1)$ である。
2．$L(G)$ の各辺 $\{e,f\}$ に、$e$ と $f$ の共通の端点 $x$ を対応させる。単純グラフなので $x$ はただ 1 つに決まる。逆に頂点 $x$ を共通の端点とする辺の組は、$x$ に接続する $d(x)$ 本の辺から 2 本を選ぶ組であり、$\binom{d(x)}2$ 個ある。$x$ ごとに数えて足せば主張を得る。
3．1 により、各辺の $L(G)$ での次数は $k+k-2$ である。$\square$

$|F|\le2$ なら、$F=\emptyset$ のときは 1 が空虚に成り立ち、$F$ が 1 本または端点を共有する 2 本のときは共有する端点が共通の頂点である。
$|F|\ge3$ とする。$F$ の 2 本 $e_1,e_2$ をとると端点を 1 つ共有するので、$e_1=ab$、$e_2=ac$（$b\ne c$）と書ける。$F$ のすべての辺が $a$ を含むなら 1 が成り立つ。そうでなければ、$a$ を含まない辺 $e_3\in F$ がある。$e_3$ は $ab$ と $ac$ の両方と端点を共有し、$a$ を含まないので $b$ と $c$ を含む。よって $e_3=bc$ である。
このとき $F$ のどの辺 $e$ も三角形の 3 辺 $ab,bc,ca$ のうち自分以外のすべてと端点を共有する。$e$ が三角形の辺でないと仮定する。$e$ は $ab,bc,ca$ の 3 本すべてと端点を共有する。$e$ の端点が両方とも $\{a,b,c\}$ に入るなら $e$ は三角形の辺になるので、$e$ の端点の一方 $x$ は $\{a,b,c\}$ の外にある。すると $e$ のもう一方の端点 $y$ が $ab$、$bc$、$ca$ のすべてに属さなければならないが、$\{a,b\}\cap\{b,c\}\cap\{c,a\}=\emptyset$ なので矛盾する。よって $F\subset\{ab,bc,ca\}$ であり、$F\supset\{ab,ac,bc\}$ と合わせて 2 が成り立つ。
$|F|\ge4$ なら 2 は起こりえないので 1 が成り立つ。$\square$

1．$L(G)$ のクリークは、どの 2 本も端点を共有する辺の集合 $F$ である。lem-lg-intersecting により、$F$ は 1 頂点 $x$ に集まる星（大きさは $d(x)\le\Delta(G)$ 以下）か三角形の 3 辺である。逆に、次数 $\Delta(G)$ の頂点に接続する辺全体は大きさ $\Delta(G)$ のクリークであり、三角形の 3 辺は大きさ 3 のクリークである。したがって $\omega(L(G))$ は、三角形がなければ $\Delta(G)$、あれば $\max\{\Delta(G),3\}$ である。三角形があれば $\Delta(G)\ge2$ なので、主張の 2 つの場合に分かれる。
2．$L(G)$ の独立集合は、どの 2 本も端点を共有しない辺の集合、すなわち $G$ のマッチングである。大きさの最大値をとれば等式を得る。
3．$\chi(L(G))=\chi'(G)$ は、彩色 の命題「辺彩色と線グラフの頂点彩色」により、$G$ の $k$-辺彩色と $L(G)$ の $k$-頂点彩色が同じ写像として一対一に対応することから従う。下界は、クリークの頂点に相異なる色が要ることと 1 から $\chi(L(G))\ge\omega(L(G))\ge\Delta(G)$ である。上界は 辺彩色 の定理「Vizing の定理」の $\chi'(G)\le\Delta(G)+1$ である。$\square$

$L(G)$ の頂点 $e=uv$ と、その 3 つの相異なる隣接頂点 $f_1,f_2,f_3$ をとる。各 $f_i$ は $e$ と端点を共有するので、$u$ か $v$ を含む。鳩の巣原理により、ある 2 つ $f_i,f_j$（$i\ne j$）が同じ端点（$u$ または $v$）を含む。すると $f_i$ と $f_j$ は端点を共有し、$L(G)$ で隣接する。よって $e,f_1,f_2,f_3$ は誘導部分グラフとして爪をなさない。$\square$

1 ⇒ 2．$H=L(G)$ としてよい。$G$ の次数 $1$ 以上の頂点 $x$ ごとに、$x$ に接続する辺全体の集合 $K_x\subset E=V(H)$ をとる。$K_x$ のどの 2 辺も $x$ を共有するので、$K_x$ は $L(G)$ のクリークである。
(a)：$L(G)$ の辺 $\{e,f\}$ について、$e$ と $f$ の共通の端点 $x$ はただ 1 つである。$\{e,f\}$ が $K_y$ の辺であることは、$e,f$ がともに $y$ を含むこと、すなわち $y$ が共通の端点であることと同値なので、$\{e,f\}$ は $K_x$ だけの辺である。
(b)：$L(G)$ の頂点 $e=xy$ が $K_z$ に属するのは $z\in\{x,y\}$ のときだけなので、$e$ はちょうど 2 つの $K_x,K_y$ に属する。
2 ⇒ 1．族 $(K_i)_{i\in I}$ が (a)(b) を満たすとする。属する $K_i$ が $2$ 個未満の頂点 $v$ ごとに、足りない個数（$2$ から属する個数を引いた数）だけ新しい添字を足して 1 点集合 $\{v\}$ を族に加え、どの頂点もちょうど 2 つの族の元に属するようにする。1 点集合はクリークであり、辺をもたないので (a) は保たれる。こうして得た族も $(K_i)_{i\in I}$ と書き、頂点 $v$ が属する添字の集合を $I_v$ とすると、$|I_v|=2$ である。
グラフ $G$ を、頂点集合を $I$、辺集合を $\{I_v: v\in V(H)\}$ として定める。各 $I_v$ は $I$ の 2 元部分集合である。
写像 $v\mapsto I_v$ は単射である。実際、相異なる $v,w$ について $I_v=I_w=\{i,j\}$ とすると、$v,w$ はともに $K_i$ と $K_j$ に属する。$v,w$ の 2 点を含むので $K_i,K_j$ は 1 点集合でなく、もとの族の元である。クリークなので $vw$ は $H$ の辺であり、$K_i$ の辺でも $K_j$ の辺でもある。$i\ne j$ なのでこれは (a) に反する。したがって $G$ は単純グラフで、$v\mapsto I_v$ は $V(H)$ から $E(G)$ への全単射である。
この全単射が隣接関係を保つことを示す。$v,w$ が $H$ で隣接するなら、(a) により辺 $vw$ はある $K_i$ の辺であり、$i\in I_v\cap I_w$ なので $I_v$ と $I_w$ は端点 $i$ を共有する。逆に $I_v$ と $I_w$（$v\ne w$）が端点 $i$ を共有するなら、$v,w\in K_i$ であり、$K_i$ はクリークなので $v,w$ は隣接する。よって $H\cong L(G)$ である。$\square$

1．$B^{\mathsf T}B$ の $(j,l)$ 成分は $\sum_iB_{ij}B_{il}$、すなわち $e_j$ と $e_l$ の共通の端点の個数である。$j=l$ なら $2$、$j\ne l$ なら端点を共有するとき $1$、しないとき $0$ である。これは $2I_m+A(L(G))$ の成分である。同様に $BB^{\mathsf T}$ の $(i,k)$ 成分は $v_i$ と $v_k$ をともに含む辺の本数で、$i=k$ なら $d(v_i)$、$i\ne k$ なら隣接するとき $1$ である。
2．$B^{\mathsf T}B$ は実対称行列で、任意の $x\in\mathbb{R}^m$ について $x^{\mathsf T}B^{\mathsf T}Bx=(Bx)^{\mathsf T}(Bx)\ge0$ なので、固有値はすべて $0$ 以上である。1 により $A(L(G))$ の固有値は $B^{\mathsf T}B$ の固有値から $2$ を引いたものなので $-2$ 以上である。また $B^{\mathsf T}B$ の階数は $B$ の階数 $\le n$ 以下なので、$m>n$ なら固有値 $0$ の重複度は $m-n$ 以上であり、$A(L(G))$ の固有値 $-2$ の重複度も $m-n$ 以上である。
3．まず、任意の実 $n\times m$ 行列 $B$ について、変数 $t$ の多項式として
$$ t^{\,n}\det(tI_m-B^{\mathsf T}B)=t^{\,m}\det(tI_n-BB^{\mathsf T}) $$
が成り立つことを示す。$t\ne0$ とし、ブロック行列 $M=\begin{pmatrix}I_n&B\\B^{\mathsf T}&tI_m\end{pmatrix}$ の行列式を 2 通りに計算する。左上の $I_n$ で掃き出すと $\det M=\det(tI_m-B^{\mathsf T}B)$、右下の $tI_m$ で掃き出すと $\det M=t^{\,m}\det(I_n-t^{-1}BB^{\mathsf T})=t^{\,m-n}\det(tI_n-BB^{\mathsf T})$ である。両辺に $t^{\,n}$ を掛けると、$0$ でない $t$ で等式が成り立つので、多項式として等しい。
$G$ が $k$-正則なら $D=kI_n$ なので $BB^{\mathsf T}=A(G)+kI_n$ の固有値は $\theta_i+k$ であり、$\det(tI_n-BB^{\mathsf T})=\prod_i(t-\theta_i-k)$ である。$k\ge2$ なら $m=kn/2\ge n$ なので、上の等式から $\det(tI_m-B^{\mathsf T}B)=t^{\,m-n}\prod_i(t-\theta_i-k)$ を得る。よって $B^{\mathsf T}B$ の固有値は $\theta_i+k$ と $m-n$ 個の $0$ であり、1 により $A(L(G))$ の固有値はそれぞれから $2$ を引いたものである。$\square$

Euler 閉路を、通る順に辺の列 $e_1,e_2,\dots,e_m$ として書く（$m=|E|\ge3$）。各 $e_i$ と $e_{i+1}$ はその間で通過する頂点を共有し、$e_m$ と $e_1$ は閉路の出発点を共有する。Euler 閉路は各辺をちょうど 1 回ずつ通るので $e_1,\dots,e_m$ は相異なり、$L(G)$ の全頂点を尽くす。したがって $e_1e_2\cdots e_me_1$ は $L(G)$ の長さ $m\ge3$ の閉路で、全頂点を 1 回ずつ通る。$\square$