圍長 (圖論)

在圖論中，一個圖的圍長定義為這個圖所包含的最短環長。 若這個圖是無環圖，它的圍長則定義做無窮大。 舉例來說，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$種色。

若不用概率論證，亦可明確構造圍長和色數皆大的圖，例如有限域上某些線性群的凱萊圖。此類例子同時屬拉馬努金圖，擴展系數大。