围长 (图论)

在图论中，一个图的围长定义为这个图所包含的最短环长。 若这个图是无环图，它的围长则定义做无穷大。 举例来说，4-环（正方形）的围长是 4。

笼 (Cage)

最小的围长为 g 的三次图（3-正则图）称做 g-笼（或是 (3,g)-笼）。佩特森图是唯一的 5-笼，Heawood graph 则是唯一的 6-笼，McGee graph 是唯一的 7-笼，Tutte eight cage 是唯一的 8-笼。 对特定的围长来说，可能会存在不只一个笼。比如，存在三个不同构的 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

围长与图染色

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

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

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