2.2　度和距離

圖G的頂點v的度，記為d_G（v），是指G中與v關聯的邊的數目，每個自環算作兩條邊。特別地，如果G是一個簡單圖，d_G（v）表示v在G中的鄰點數目。在沒有歧義的情況下，一般僅僅簡寫為d（v）。稱圖G是k正則的，如果對所有v∈V，有d（v）=k;正則圖是指對某個k而言的k正則圖。度為0的點稱為孤立點。用δ（G）和Δ（G）分別表示G中頂點的最小度和最大度。圖G中兩個頂點u，v的距離d_G（u，v）表示的是在G中最短的u-v路的長度;如果沒有這樣的路存在，令d_G（u，v）:=∞。G的直徑diam（G）是指G中任意兩個頂點之間距離的最大值。