部分グラフ
概要
グラフ $G$ の部分グラフとは、頂点集合および辺集合がそれぞれ $G$ の頂点集合と辺集合の部分集合になっているグラフである。
グラフ $G^\prime=(V^\prime, E^\prime)$ がグラフ $G=(V, E)$ の部分グラフ (subgraph) であるとは、$V^\prime\subset V$ かつ $E^\prime\subset E$ となることである。このことを、単に $G^\prime\subset G$ によりあらわす。
とくに、$E$ に属する辺で、$V^\prime$ の頂点同士を結ぶものをすべて含むグラフ、つまり $E^\prime=E\cap [V^\prime]^2$ となる部分グラフ $G^\prime=(V^\prime, E^\prime)$ を、$V^\prime$ により誘導される (induced) 部分グラフといい、$G[V^\prime]$ によりあらわす。
また、$V^\prime=V$ となる部分グラフ $(V, E^\prime)$ を、$G$ の全域的な (spanning) 部分グラフという。
$\abs{V}=n$ かつ、$\abs{E}>\floor{n^2/4}$ となるグラフは三角形を部分グラフにもつ。言い換えれば、三角形を部分グラフにもたない位数 $n$ のグラフの大きさは $\floor{n^2/4}$ 以下である。
$G$ が三角形を部分グラフにもたないグラフとする。このとき、$xy\in E$ ならば $x$ と $y$ の両方に隣接する頂点は存在しないから、
$$d(x)+d(y)\leq n$$
となる。すべての辺 $xy\in E$ について、これを加えると、
$$\sum_{xy\in E}d(x)+d(y)\leq n\abs{E}$$
となる。一方、各 $x\in E$ について、左辺の和にあらわれる $d(x)$ の回数は、$x$ の次数に等しい。つまり
$$\sum_{xy\in E}d(x)+d(y)=\sum_{x\in V}\sum_{y\in\Gamma(x)}d(x)=\sum_{x\in V}d(x)^2$$
となる。よって
$$\sum_{x\in V}d(x)^2\leq n\abs{E}$$
となる。
次数に関する定理1
より、
$$\sum_{x\in V}d(x)=2\abs{E}$$
となるから、Cauchyの不等式より
$$(2\abs{E})^2=\left(\sum_{x\in V}d(x)\right)^2\leq n\sum_{x\in V}d(x)^2\leq n^2\abs{E}$$
が成り立つ。それで
$$\abs{E}\leq n^2/4$$
となる、$\abs{E}$ は整数だから
$$\abs{E}\leq\floor{n^2/4}$$
でなければならないことがわかる。
一方、完全二部グラフ $K_{n/2, n/2}$ あるいは $K_{(n+1)/2, (n-1)/2}$ は、$\abs{E}=\floor{n^2/4}$ となるが、三角形を部分グラフにもたないことがすぐにわかる。
このように、あるグラフ $F$ （あるいはそれと同形な）グラフを部分グラフ、あるいは誘導部分グラフなどの部分構造としてもたないという条件を禁止部分構造 (forbidden substructure) という。
とくに、あるグラフ $F$ と同形なグラフを部分グラフとしてもたない、位数 $n$ のグラフの最大の大きさを決定する問題を禁止部分グラフ問題 (forbidden subgraph problem) という。
一般に、ある部分構造をもつ、あるいはもたないという条件を満足するグラフの辺の個数や最小次数、最大次数などの性質を考察する理論を極値グラフ理論 (extremal graph theory) といい、グラフ理論の非常に重要な一分野となっている。
