围长 (图论)

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

笼 (Cage)

最小的围长为 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），扩展系数大。

参考文献

1. R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
2. Weisstein, Eric W. (编). Girth. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2017-06-16]. （原始内容存档于2020-08-04） （英语）.
3. Brouwer, Andries E., Cages, [2017-06-16], （原始内容存档于2020-08-04）.
4. Erdős, Paul. Graph theory and probability [图论与概率]. Canadian Journal of Mathematics. 1959, 11: 34–38. doi:10.4153/CJM-1959-003-9 （英语）.
5. Davidoff, Giuliana; Sarnak, Peter; Valette, Alain, Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts 55, Cambridge University Press, Cambridge, 2003, ISBN 0-521-82426-5, MR 1989434, doi:10.1017/CBO9780511615825