圍長(girth)是圖論中的一個概念，指在一個無向圖中，最短的環的長度。如果圖中不含任何環，則定義其圍長為無限大。例如，一個正方形的圍長為4，而一個三角格線的圍長為3。顯而易見的，一個圍長為4的圖不含三角形。
基本介紹
定義,籠,關係,定理,
定義
圍長(girth)是圖論中的一個概念，指在一個無向圖中，最短的環的長度。
籠
圍長為g的最小的三次圖（度為三的正則圖）被稱為g-籠（g-cage），又被稱為(3,g)-籠（(3,g)-cage）。著名的彼得森圖（Peterson Graph）就是最小的5-籠。一個圍長對應籠的個數不一定為1，例如圍長為10時，存在三種不同構的籠。
彼德森圖(Peterson Graph)
關係
直觀上，圍長越長，意味著圖較為稀疏，染色數可能會偏多。但Erdős在1959年的論文中提出了，對於任意的k和l，存在一個圖，滿足其圍長大於l，且其染色數大於k。後來又有人提出了更緊的界。
定理
命題1.3.2：任意包含至少一個圈的圖滿足g(G)≤2diam(G)+1。
證明：設C為G的一個最短圈．如果g(G)≥2diam(G)+2,則C包含兩個頂點使得它們在C 中的距離至少是diam(G)+1. 在G中，這兩個頂點之間的距離更短，而連線它們之間的最短路P不是C的子圖，所以P包含一條C-路xPy。將C中兩條x-y路中短的一條與路xPy連線在一起，將形成一個比C更短的圈，矛盾.
圖G的中心點是指能使得它到任何其他頂點的距離儘可能小的頂點，這個最短距離稱為半徑並記為radG.所以，嚴格地說，
.
命題1.3.3：設G是一個半徑至多為k且最大都至多為d＞=3的圖，則G的頂點個數小於
.
證明： 設z是G的一個中心點而
是G中到z距離為i的頂點集，則
.顯然
=1且
<=d.對每個i>=1，因為
中的每個頂點均為中的某個頂點的鄰點，且的每個頂點在中至多有d-1個鄰點（由於它還有一個鄰點在
中），所以
。對所有i＜k用歸納假設，有
，這蘊含著
.
類似地，假設G的最小度和圍長均較大，可找到G的階的下界。
定理1.3.4(Alon,Hoory and Linial,2002)：
設G是一個圖。如果
且
,則
。
定理1.3.4保證了一個相對於|G|的較短圈的存在性。可以得到以下更一般的界：
推論1.3.5：若
，則
.
證明：如果g:=g(G)是偶數，則
當g是奇數時，
因為
，故結論成立。
