次数 (グラフ理論)

グラフ理論における次数（じすう、）は、グラフの頂点に接合する辺の数を意味し、ループであれば2回カウントされる。頂点 formula_1 の次数を formula_2 と表記する。グラフ "G" の最大次数を Δ("G") と表記し、その中の頂点群の最大次数を意味する。また、グラフの最小次数は δ("G") と表記し、その中の頂点群の最小次数を意味する。右のグラフでは、最大次数は3、最小次数は0である。正則グラフでは全頂点の次数が等しく、その次数をグラフの次数と呼ぶこともある。
有向グラフでは、頂点に入ってくる辺数を入次数 (indegree)、頂点から出て行く辺数を出次数 (outdegree) と呼ぶ。
握手補題.
グラフ formula_3 の次数の総和は次の公式で表される。
これの証明は という手法（二通りに数え上げる）の例である。グラフ内の辺と頂点の接合の個数は式の左辺のように各頂点の次数の総和でも表されるし、右辺のように辺の両端を数え上げてもよい。
この公式が意味するのは、次数が奇数の頂点の個数は偶数個だということである。これを握手補題 (handshaking lemma) と呼ぶ。この補題の名称は、あるグループ内で奇数人の人々と握手した人の数は常に偶数になるという数学の証明問題に由来する。
次数列.
無向グラフの次数列 (degree sequence) とは、そのグラフの頂点の次数を増加しない順序で並べた数列である。上のグラフでは (3, 3, 3, 2, 2, 1, 0) となる。次数列はグラフ不変量であり、同型のグラフは同じ次数列を有する。しかし、一般に次数列だけでグラフを一意に特定することはできない。同型でないグラフでも同じ次数列になりうる。
次数列問題とは、正の整数の増加しない数列を次数列として与えたとき、対応するグラフの実例（または全てのグラフ）を求める問題である。次数として0を許容すると単に独立した頂点を加えればよいだけなので、出題する場合には0は使わない。
与えられた次数列に対応するグラフの個数を求める（あるいは推測する）問題は、グラフの数え上げ問題の一種である。
次数の総和の公式から、総和が奇数となるような数列（例えば (3, 3, 1)）はグラフの次数列としてはあり得ないことが分かる。逆もまた真であり、数列の総和が偶数であれば、グラフの次数列としてありうる。
ループや多重辺を許容すれば次数列からグラフを描くことは簡単だが、単純グラフ (simple graph) に限定すると次数列問題はやや難しくなる。数列 (8, 4) は明らかに単純グラフの次数列ではない。何故なら Δ(G) が頂点数から1を引いた値より大きいという矛盾があるためである。数列 (3, 3, 3, 1) も単純グラフの次数列ではないが、こちらの理由は前者ほど明らかではない。単純グラフの次数列の一般的基準を求めることは古典的問題であり、Erdős and (1960)、 (1955)、 (1961)、 and Sierksma et al. (1991) などの例がある。
例えば、Erdős-Gallai の定理では、数列 (di)i=1...,n は、総和が偶数でかつ 1 と n の間の全ての k について
であるときのみ単純グラフの数列である。Havel と Hakimi は、(d2-1,d3-1...,dd1+1-1,dd1+2, dd1+3...,dn) が単純グラフの次数列であるときだけ (d1,d2...,dn) が単純グラフの次数列であることを証明した。