ケージ (グラフ理論)
次数1のグラフはサイクルを持たない。次数2のグラフはサイクルそのもので内周は頂点数に一致する。そのためr ≥ 3の場合についてケージを考える。(r,3)-ケージは頂点数r+1の完全グラフKr+1となる。また(r,4)-ケージは頂点数2rの完全二部グラフKr,rとなる。
他の特筆すべきケージ(ムーアグラフを含む。):
(3,5)-ケージ: ピーターセングラフ、頂点数10
(3,6)-ケージ: ヒーウッドグラフ、頂点数14
(3,7)-ケージ: マギーグラフ、頂点数24
(3,8)-ケージ: Tutte–Coxeter graph、頂点数30
(3,10)-ケージ: バラバン10-ケージ、頂点数70
(4,5)-ケージ: ロバートソングラフ、頂点数19
(7,5)-ケージ: ホフマン-シングルトングラフ、頂点数50
r-1が素数のべき乗のとき、(r,6)-ケージは射影平面のインシデント・グラフとなる。
r-1が素数のべき乗のとき、(r,8)-ケージと(r,12)-ケージは一般化多角形となる。
r > 2かつg > 2の場合に知られている(r,g)-ケージの頂点数を次表にまとめる。ただし射影平面と一般化多角形によるものは除く。