前へ / 戻る / 次へ

彩色数の上限についての定理

証明　頂点数についての帰納法で示します。
　頂点 $v$ を 1 つ取り $G'=G-v$ とおくと、$G'$ の頂点の次数も $\rho$ 以下ですから 帰納法の仮定により $\chi(G') \leqq \rho +1$. です。 そこで、$G'$ を $\rho+1$ 色以下で点彩色しておくと、 $v$ の隣接点は $\rho$ 個以下なので $\rho+1$ 色のうち $v$ に塗れる色がまだ残っています。(証明終)

　例えば次のグラフでは $\rho=4$ です：

	→		→
$G$		$G'=G-v$ を 5 色で点彩色しておく		$v$ には 5 が塗れる

　$G$ が完全グラフでないときはこの上限はあと 1 つ下げることができます。 　証明はテキストの §18 にありますが、とても長いので省略します。

前へ / 戻る / 次へ