隣接・次数

$uv\in E(G)$ のとき $u$ と $v$ は隣接するといい、$v$ と辺 $uv$ は接続するという。頂点 $v$ の近傍を $N(v)=\{u\in V(G): uv\in E(G)\}$、次数を $d(v)=|N(v)|$（多重グラフでは $v$ に接続する辺の本数）と定める。最小次数を $\delta(G)=\min_v d(v)$、最大次数を $\Delta(G)=\max_v d(v)$ と書く。すべての頂点の次数が $k$ のグラフを $k$-正則という。