圍長 (圖論)

在图论中，一個圖的圍長定義為這個圖所包含的最短環長。^[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