◎グラフの彩色：隣接する頂点には異なる色を塗るという条件ですべての頂点に色を割り当てること。k 色を使って彩色できたとき，そのグラフは k-彩色可能であるという。
k-彩色可能なグラフは，k 色より多くの色を使っても彩色は可能である。一方，k 色より少ない色を使った場合は，彩色不可能になることがある。
◎グラフの染色数：彩色するのに必要な色の最小数。グラフ G の染色数を χ(G) と表す。χ は，ローマ字の x ではなく，ギリシャ文字で“カイ”と読む。
◎Welch-Powell の彩色アルゴリズム
(Step 1) 次数が大きい順（降順，descending order）に頂点を並べる。
(Step 2) 色１を頂点列の最初の頂点に割り当て，以下は，頂点列の順番に色１が塗れるもの（つまり，色１が既に割り当てられている頂点とは隣接しない頂点）にだけ色１を割り当てる。頂点列の最後まで来たら終わり。
(Step 3) 頂点列の先頭から調べて，色２を塗れるものにだけ割り当てる。
(Step 4) 以下，同様にしてすべての頂点に色が割り当てられるまで続ける。
◎２-彩色可能なグラフは２部グラフであり，２部グラフに含まれる閉路長は常に偶数であり，閉路長がすべて偶数であるグラフは２-彩色可能である。
◎四色定理：すべての平面的グラフは４-彩色可能である。
この定理は，1976年にコンピュータを使って証明されたとして有名である。
◎木：閉路をもたない連結グラフ。定理 6.8 と 6.9 に木がもつ性質がまとめられている。木に含まれる辺の本数は頂点数より１だけ小さい。