ピーターセングラフ

ピーターセングラフ
	典型的なピーターセングラフ。五角形の中に五芒星形を描き、対応する各頂点を結ぶ。
命名者	ジュリウス・ピーターセン
頂点	10
辺	15
半径	2
直径	2
内周	5
自己同型	120 (S5)
彩色数	3
彩色指数	4
分数彩色指数	3
特性	正則グラフ; 強正則グラフ; スナークグラフ
	テンプレートを表示

ピーターセングラフ（英: Petersen graph）またはペテルセングラフとは、10個の頂点と15個の辺からなる無向グラフである。グラフ理論の様々な問題の例、あるいは反例としてよく使われる。1898年、ジュリウス・ピーターセンが3色辺彩色できない最小のブリッジのない3-正則グラフとして考案した^[1]。そのため、ピーターセングラフと呼ばれているが、実際には1886年に既に考案されていた^[2]。

構成

ピーターセングラフは $K_{5}$ の線グラフ（英語版）の補グラフである。また、 $KG_{5,2}$ のクネーザーグラフでもある。すなわち、5元の集合の2元部分集合それぞれについて頂点を割り当て、互いに素な部分集合に対応する頂点同士を辺で結ぶと、ピーターセングラフになる。

幾何学的には、半十二面体（英語版）の頂点と辺をグラフで表したものと言える。すなわち、正十二面体の反対側の点、線、面を同じと識別したものである。

埋め込み

ピーターセングラフは平面グラフではない。一般に非平面グラフなら、マイナーとして $K_{5}$ の完全グラフか $K_{3,3}$ の完全2部グラフがあるが、ピーターセングラフでは両方同時にマイナーとして持つ。 $K_{5}$ マイナーは、完全マッチングの辺を縮約することで形成され、一番上の図で言えば、短い辺を縮約すればよい。 $K_{3,3}$ マイナーは、1つの頂点を削除し（例えば、3回対称の図の中央の頂点）、削除した頂点と隣接していた頂点に付随する辺を縮約することで形成される。

最も典型的なピーターセングラフの描き方は、正五角形の中に五芒星形を描く描き方だが、これでは5箇所で辺が交差する。しかし、もっと交差を少なくする描き方もある。右には交差が2つしかない図も示している。これが最小なので、ピーターセングラフの交叉数（英語版）は2である。トーラス上では全く交差させずにピーターセングラフを描ける。つまり、向きのある種数が1である。

ピーターセングラフは（交差はあるが）平面上で全ての辺が同じ長さとなるよう描ける。すなわち、単位距離グラフである。

ピーターセングラフを交差なしに埋め込める最も単純な向き付け不能曲面は、射影平面である。これはピーターセングラフを半十二面体で構築する際に得られる埋め込みである。射影平面埋め込みは、通常のピーターセングラフの中心にクロスキャップを置き、五芒星の辺をクロスキャップに沿わせることでも得られる。この場合、6個の五角形の面が現れる。以上からピーターセングラフは向きのない種数も1である。

対称性

ピーターセングラフは強正則グラフである。また、辺推移的かつ頂点推移的という意味で対称グラフでもある。また、14ある3-正則の距離正則グラフ（英語版）の一つである^[3]。

ピーターセングラフの自己同型群（英語版）は対称群 $S_{5}$ である。ピーターセングラフ上の $S_{5}$ の振る舞いは、クネーザーグラフとしてのそれに従う。隣接する頂点を区別しないピーターセングラフの全ての準同型（英語版）は自己同型である。図に示しているように、ピーターセングラフは5回対称としても3対称としても描けるが、対称群全体を表すような図を平面に描くことはできない。

ピーターセングラフは高い対称性があるがケイリーグラフではない。ケイリーグラフでない連結頂点推移グラフとしては最小である。

ハミルトン路とハミルトニアン閉路

ピーターセングラフにはハミルトン路はあるがハミルトン閉路はない。ハミルトン閉路がなく、ブリッジ（それを削除するとグラフが2つの連結グラフに分かれてしまうという辺）のない3-正則グラフとしては最小である。また、頂点を1つ削除するとハミルトングラフになるので、準ハミルトングラフであり、準ハミルトングラフとしても最小である。

ピーターセングラフは、5種類しか知られていないハミルトン閉路を持たない連結頂点推移グラフである。その5種類以外にそのようなグラフは存在しないという予想がなされている。2-連結で r-正則のグラフで、最大 3r + 1 の頂点を持つグラフは、ハミルトングラフかピーターセングラフのどちらかである^[4]。

彩色

ピーターセングラフの頂点を3色に彩色した様子

ピーターセングラフの彩色数は 3 であり、隣接する頂点が同じ色にならないようにグラフ彩色したとき、最低でも3色を必要とする。

ピーターセングラフの彩色指数（英語版）は 4 である。すなわち、辺彩色では4色が最小の色数である。この証明には4つのケースを具体的に示して、3色では彩色できないことを示す。彩色指数が 4 のブリッジのない連結3-正則グラフであることから、ピーターセングラフはスナーク（英語版）であり、スナークとしては最小である。また、1946年までピーターセングラフ以外のスナークは知られていなかった。W. T. Tutte のスナーク予想（全てのスナークはマイナーとしてピーターセングラフを持つ）は、2001年に Robertson, Sanders, Seymour, Thomas が証明し、スナーク定理となった^[5]。

その他の性質

3-連結でブリッジを持たない。
独立数は 4 で、3-部グラフである。
3-正則グラフであり、支配集合問題は 3 で、完全マッチングがある。
半径 2 で直径 2 である。直径 2 の3-正則グラフとしては最大である。
グラフのスペクトルは −2, −2, −2, −2, 1, 1, 1, 1, 1, 3 である。
内周5 の 3-正則グラフとしては最小である。唯一の $(3,5)$ -ケージであり、10個しか頂点がないことから、唯一の $(3,5)$ -ムーアグラフである。
全域木は2000あり、10頂点の3-正則グラフの中で最大である^[6]^[7]。
1-因子分解可能ではない（1-因子分解不可能である）。（＝完全マッチングのパターン3種のみで構成できない。）

注釈・出典

^ Brouwer, Andries E., The Petersen graph
^ Kempe, A. B. (1886), “A memoir on the theory of mathematical form”, Philosophical Transactions of the Royal Society of London 177: 1–70, doi:10.1098/rstl.1886.0002
^ Cubic symmetric graphs (The Foster Census)
^ Holton, D. A.; Sheehan, J. (1993年), The Petersen Graph, Cambridge University Press, ISBN 0-521-43594-3 , page 32.
^ Pegg, Ed, Jr. (2002年), “Book Review: The Colossal Book of Mathematics”, Notices of the American Mathematical Society 49 (9): 1084-1086 .
^ Jakobson, Dmitry; Rivin, Igor (1999年), On some extremal problems in graph theory, arXiv:math.CO/9907050
^ Valdes, L. (1991年), “Extremal properties of spanning trees in cubic graphs”, Congressus Numerantium 85: 143-160

参考文献

Exoo, Geoffrey; Harary, Frank; Kabell, Jerald (1981年), “The crossing numbers of some generalized Petersen graphs”, Mathematica Scandinavica 48: 184–188
Coxeter, H. S. M. (1950年), “Self-dual configurations and regular graphs”, Bulletin of the American Mathematical Society 56: 413-455, doi:10.1090/S0002-9904-1950-09407-5
Keller, Mitch. Kneser graphs on PlanetMath
Lovász, László (1993年), Combinatorial Problems and Exercises (2nd ed.), North-Holland, ISBN 0-444-81504-X
Petersen, Julius (1898年), “Sur le théorème de Tait”, L'Intermédiaire des Mathématiciens 5: 225–227
Watkins, Mark E. (1969年), “A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs”, Journal of Combinatorial Theory 6: 152–164
Weisstein, Eric W. "Petersen Graph". mathworld.wolfram.com (英語).

[1] Brouwer, Andries E., The Petersen graph

[2] Kempe, A. B. (1886), “A memoir on the theory of mathematical form”, Philosophical Transactions of the Royal Society of London 177: 1–70, doi:10.1098/rstl.1886.0002

[3] Cubic symmetric graphs (The Foster Census)

[4] Holton, D. A.; Sheehan, J. (1993年), The Petersen Graph, Cambridge University Press, ISBN 0-521-43594-3 , page 32.

[5] Pegg, Ed, Jr. (2002年), “Book Review: The Colossal Book of Mathematics”, Notices of the American Mathematical Society 49 (9): 1084-1086 .

[6] Jakobson, Dmitry; Rivin, Igor (1999年), On some extremal problems in graph theory, arXiv:math.CO/9907050

[7] Valdes, L. (1991年), “Extremal properties of spanning trees in cubic graphs”, Congressus Numerantium 85: 143-160

[1]

[2]

[3]

[4]

[5]

[6]

[7]