§D3.16行列木定理と全域木の個数

証明.$A \cdot \operatorname{adj} A$の$(i, k)$成分は$\sum_{j} a_{ij} C_{kj}$である。

$i = k$のとき、これは第$i$行に沿った余因子展開そのものであり、値は$\det A$である。

$i \ne k$のとき、$A$の第$k$行を第$i$行で置き換えて得られる行列を$B$とする。$B$から第$k$行を除いた部分は$A$から第$k$行を除いた部分と一致するので、$B$の$(k, j)$余因子は$C_{kj}$に等しい。したがって$B$の第$k$行に沿った余因子展開は$\sum_j a_{ij} C_{kj}$である。ところが$B$は第$i$行と第$k$行が等しいので、行列式の交代性より$\det B = 0$である。よって$\sum_j a_{ij} C_{kj} = 0$となる。

以上より$A \cdot \operatorname{adj} A = (\det A) I$が成り立つ。列に沿った余因子展開について同じ議論を行えば$\operatorname{adj} A \cdot A = (\det A) I$を得る。▨

証明. 成分がすべて$1$である列ベクトルを$\mathbf{1}$と書く。$L$の各行の成分の和は$0$であるから$L\mathbf{1} = \vec 0$である。$\mathbf{1} \ne \vec 0$なので$L$は正則でなく、したがって$\det L = 0$である。補題 2.1より

が成り立つ。$L$の階数によって場合を分ける。

$\operatorname{rank} L = n - 1$の場合。§D3.10 系 4.1より$\ker L$の次元は$1$であり、$\mathbf{1} \in \ker L$かつ$\mathbf{1} \ne \vec 0$であるから$\ker L = \{ t\mathbf{1} : t \in \R\}$である。等式$L \cdot \operatorname{adj} L = O$は$\operatorname{adj} L$の各列が$\ker L$に属することを述べているので、$\operatorname{adj} L$の各列は$\mathbf{1}$のスカラー倍であり、各列の成分はその列の中ですべて等しい。また$\operatorname{adj} L \cdot L = O$より、$\operatorname{adj} L$の各行ベクトル$\vec r^\top$は$\vec r^\top L=\vec 0^\top$を満たす。$L^\top=L$なので$L\vec r=\vec 0$、すなわち$\vec r\in\ker L=\operatorname{span}\{\mathbf 1\}$であり、各行の成分もその行の中ですべて等しい。列の中で等しく、かつ行の中で等しいので、$\operatorname{adj} L$の成分はすべて等しい。

$\operatorname{rank} L \le n - 2$の場合。$L$から1行と1列を除いて得られる$n-1$次行列を$L'$とする。行を1本除いても列ベクトルの間に成り立つ一次関係は保たれるので列階数は増えず、列を1本除いても列の部分集合を取るだけなので列階数は増えない。よって$\operatorname{rank} L' \le \operatorname{rank} L \le n-2 < n-1$であり、$L'$は正則でないから$\det L' = 0$である。したがってすべての余因子が$0$であり、$\operatorname{adj} L = O$となる。

いずれの場合も$\operatorname{adj} L$の成分はすべて等しい。$\operatorname{adj} L$の$(i, j)$成分は$C_{ji}$であったから、$L$のすべての余因子が等しい。▨

証明.$G$の全域木を、$e$を含まないものと含むものに分ける。

$e$を含まない全域木の全体は、$G - e$の全域木の全体と一致する。実際、$e$を含まない辺の部分集合$F$について、$(V, F)$が連結であるという条件も、閉路をもたないという条件も、$G$で考えても$G - e$で考えても同じ条件である。よって、この部分の個数は$\tau(G-e)$である。

$e$を含む全域木$F$に対し、$\varphi(F) = F \setminus \{e\}$を$G/e$の辺の集合とみなす。

$\varphi(F)$が$G/e$の全域木であることを示す。連結性については、$G/e$の2頂点を取り、それらのもとになる$G$の頂点を$(V, F)$の道で結び、その道を$G/e$へ読み替えればよい。道が$e$を通る場合、その部分は頂点$w$に潰れる。次に$\varphi(F)$が閉路$C$をもったとして矛盾を導く。$C$の辺は$F \setminus \{e\}$の辺である。$C$が$w$を通らなければ、$C$はそのまま$(V, F)$の閉路であり、$F$が全域木であることに反する。$C$が$w$を通る場合、$C$の辺を$G$へ戻すと、$u$または$v$から出て$u$または$v$へ戻る道が得られる。両端が同じ頂点であれば$(V, F)$の閉路になり矛盾する。両端が$u$と$v$であれば、その道に$e$を加えたものが$(V, F)$の閉路になり、やはり矛盾する。

逆に$G/e$の全域木$F'$に対し、$\psi(F') = F' \cup \{e\}$を$G$の辺の集合とみなす。$w$を端点としていた辺は、$G$における端点$u$または$v$へ戻す。$(V, \psi(F'))$は連結である。実際、$F'$が$G/e$を連結にしており、$e$が$u$と$v$を結ぶからである。閉路をもたないことを示す。閉路$C$があったとする。$C$が$e$を含まない場合を2つに分ける。$C$が$u$と$v$の一方しか通らないかどちらも通らなければ、$C$を$G/e$へ読み替えたものは頂点も辺も相異なるままであり、$F'$の閉路になって矛盾する。$C$が$u$と$v$の両方を通れば、$C$は$u$と$v$によって2本の道に分かれ、$e \notin C$よりどちらの道も辺を1本以上もつ。一方の道を$G/e$へ読み替えると、$w$を出て$w$へ戻り、途中の頂点と辺がすべて相異なる閉路になるので、やはり矛盾する。$C$が$e$を含む場合、$e$はループでないので$C$は2本以上の辺をもち、$C$から$e$を除くと$u$と$v$を結ぶ長さ$1$以上の道が残る。この道を$G/e$へ読み替えると$w$を出て$w$へ戻る閉路になり、矛盾する。

$\varphi$と$\psi$は互いに逆であるから、$e$を含む全域木の個数は$\tau(G/e)$である。 2つの場合を合わせて$\tau(G) = \tau(G-e) + \tau(G/e)$を得る。▨

証明. ループでない辺の本数についての帰納法で示す。主張は、頂点の個数$n \ge 1$と根$r$の取り方を問わずに証明する。

ループでない辺が$0$本の場合。$n = 1$ならば$L_r(G)$は$0$次行列であり$\det L_r(G) = 1$である。一方、辺の集合として空集合が唯一の全域木であるから$\tau(G) = 1$となり、一致する。$n \ge 2$ならば$L(G) = O$なので$L_r(G)$は$1$次以上の零行列であり$\det L_r(G) = 0$である。また相異なる2頂点を結ぶ道が存在しないので連結な全域部分グラフは存在せず、$\tau(G) = 0$となり、一致する。

ループでない辺が1本以上ある場合。そのような辺$e$を1本取り、端点を$u$と$v$とする。このとき$n \ge 2$である。命題 2.2より$\det L_r(G)$は$r$の取り方によらないので、$r = v$の場合を示せばよい。

$L(G)$と$L(G-e)$を比べると、$e$は$(u,u)$成分と$(v,v)$成分に$+1$を、$(u,v)$成分と$(v,u)$成分に$-1$を寄与する。第$v$行と第$v$列を除いた$L_v$においては、$e$の寄与は$(u,u)$成分の$+1$だけである。すなわち、$L_v(G)$の第$u$列は$L_v(G-e)$の第$u$列に、第$u$成分が$1$で他が$0$であるベクトル$\vec\varepsilon$を加えたものであり、他の列は両者で一致する。行列式の第$u$列についての線形性より

となる。ここで$N$は、$L_v(G)$の第$u$列を$\vec\varepsilon$で置き換えた行列である。

$\det N$を第$u$列に沿って余因子展開すると、$\vec\varepsilon$の$0$でない成分は第$u$成分だけであるから、$\det N$は$N$から第$u$行と第$u$列を除いた行列の行列式に等しい。これは$L(G)$から第$u$行と第$u$列、第$v$行と第$v$列を除いた行列にほかならない。

この行列が$L_w(G/e)$に等しいことを確かめる。$i, j \notin \{u, v\}$に対し、$G/e$において$i$と$j$を結ぶ辺の本数は$G$におけるそれと等しい。また$i \notin \{u, v\}$に対し、$G/e$における$i$の次数も、$G$におけるそれと等しい。$i$に接続する辺は、他方の端点が$w$へ読み替えられるだけで本数が変わらず、$i$のループの本数も変わらないからである。よって両者の成分は一致する。

$G - e$はループでない辺が$G$より1本少なく、$G/e$ではループでない辺のうち$e$が消え、$e$に平行であった辺がループへ変わるので、いずれも帰納法の仮定を適用することができる。したがって

となり、補題 3.2より右辺は$\tau(G)$に等しい。▨

証明.$G$が連結でないとする。全域木$F$が存在すれば$(V, F)$は連結であり、$F \subseteq E$より$G$自身も連結になる。これは仮定に反するので$\tau(G) = 0$である。

$G$が連結であるとする。辺の本数についての帰納法で$\tau(G) \ge 1$を示す。$G$が閉路をもたなければ、$E$自身が全域木であり$\tau(G) \ge 1$である。$G$が閉路$C$をもつならば、$C$の辺$e$を1本取る。$G - e$は連結である。実際、$e$を通る道があれば、その$e$の部分を$C$の残りの辺がなす道で置き換えることができるからである。辺の本数が減ったので帰納法の仮定より$\tau(G-e) \ge 1$であり、$G - e$の全域木は$G$の全域木でもあるから$\tau(G) \ge 1$である。▨