ピーターセングラフ
ピーターセングラフの彩色数は 3 であり、隣接する頂点が同じ色にならないようにグラフ彩色したとき、最低でも3色を必要とする。
ピーターセングラフの彩色指数(英語版)は 4 である。すなわち、辺彩色では4色が最小の色数である。この証明には4つのケースを具体的に示して、3色では彩色できないことを示す。彩色指数が 4 のブリッジのない連結3-正則グラフであることから、ピーターセングラフはスナーク(英語版)であり、スナークとしては最小である。また、1946年までピーターセングラフ以外のスナークは知られていなかった。W. T. Tutte のスナーク予想(全てのスナークはマイナーとしてピーターセングラフを持つ)は、2001年に Robertson, Sanders, Seymour, Thomas が証明し、スナーク定理となった。
ピーターセングラフ(英: Petersen graph)またはペテルセングラフとは、10個の頂点と15個の辺からなる無向グラフである。グラフ理論の様々な問題の例、あるいは反例としてよく使われる。1898年、ジュリウス・ピーターセンが3色辺彩色できない最小のブリッジのない3-正則グラフとして考案した。そのため、ピーターセングラフと呼ばれているが、実際には1886年に既に考案されていた。