围长 (图论)

最小的围长为 g 的三次图（3-正则图）称做 g-笼（或是 (3,g)-笼）。佩特森图是唯一的 5-笼，Heawood graph 则是唯一的 6-笼，McGee graph 是唯一的 7-笼，Tutte eight cage 是唯一的 8-笼。^[3] 对特定的围长来说，可能会存在不只一个笼。比如，存在三个不同构的 10-笼，分别都有 70 条边：Balaban 10-cage、Harries graph、Harries–Wong graph。

•  

  The Petersen graph has a girth of 5

•  

  The Heawood graph has a girth of 6

•  

  The McGee graph has a girth of 7

•  

  The Tutte–Coxeter graph (Tutte eight cage) has a girth of 8

给定任意正整数${\displaystyle g}$ 和${\displaystyle \chi }$ ，存在一幅图，其围长不小于${\displaystyle g}$ ，同时色数不小于${\displaystyle \chi }$ 。例如，格勒奇图（英语：Grötzsch graph）无三角形，且色数为${\displaystyle 4}$ ，然后重复采用梅切尔斯基（英语：Mycielskian）构造法（格勒奇图亦是以此法可得），即得任意大色数而无三角形的图。埃尔德什·帕尔最先用概率方法（英语：probabilistic method）证明一般的结论：^[4]

取${\displaystyle n}$ 个顶点的随机图，每两点之间各自独立地以${\displaystyle n^{(1-g)/g}}$ 概率连边，则当${\displaystyle n}$ 趋向无穷时，大概率（趋向于${\displaystyle 1}$ ）该图中 长度不逾${\displaystyle g}$ 的环总数不超过${\displaystyle n/2}$ ，同时没有${\displaystyle n/(2k)}$ 大小的独立集。所以，在每个短环中移除一点，余下的子图至少有${\displaystyle n/2}$ 点，围长大于${\displaystyle g}$ ，但染色时，每种颜色的点数不能超过${\displaystyle n/(2k)}$ ，即需要至少${\displaystyle k}$ 种色。

若不用概率论证，亦可明确构造围长和色数皆大的图，例如有限域上某些线性群的凯莱图。^[5]此类例子同时属拉马努金图（英语：Ramanujan graphs），扩展系数大。