次数 (グラフ理論)
何故なら Δ(G) が頂点数から1を引いた値より大きいという矛盾があるためである。数列 (3, 3, 3, 1) も単純グラフの次数列ではないが、こちらの理由は前者ほど明らかではない。単純グラフの次数列の一般的基準を求めることは古典的問題であり、Erdős and Gallai (1960)、V. J. Havel (1955)、S. L. Hakimi (1961)、S. A. Choudum and Sierksma et al. (1991) などの例がある。
例えば、Erdős-Gallai の定理では、数列 (di)i=1,...,n は、総和が偶数でかつ 1 と n の間の全ての k について
∑ i = 1 k d i ≤ k ( k − 1 ) + ∑ i = k + 1 n min ( d i , k ) {\displaystyle \sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k)}
であるときのみ単純グラフの数列である。Havel と Hakimi は、(d2-1,d3-1,...,dd1+1-1,dd1+2, dd1+3,...,dn) が単純グラフの次数列であるときだけ (d1,d2,...,dn) が単純グラフの次数列であることを証明した。
全ての頂点が同じ次数 k {\displaystyle k} であるようなグラフをk-正則グラフと呼び、グラフ自体の次数が k {\displaystyle k} とされる。
無向連結グラフがオイラー路を持つとき、奇数の次数の頂点は0個または2個だけである。奇数次数の頂点が0個の場合、そのオイラー路はオイラー閉路である。
有向グラフがpseudoforestであるとき、各頂点の出次数は高々1である。全頂点の出次数が1のpseudoforestを functional graph と呼ぶ。
Brooks' theorem によれば、クリークや奇閉路以外の任意のグラフのグラフ彩色数は高々 Δ であり、Vizing's theorem によれば、任意のグラフの彩色指数は高々 Δ + 1 である。