各頂点に次数を記したグラフ グラフ理論における次数(じすう、英: degree, valency)は、グラフの頂点に接合する辺の数を意味し、ループであれば2回カウントされる[1]。頂点 の次数を と表記する。グラフ G の最大次数を Δ(G) と表記し、その中の頂点群の最大次数を意味する。また、グラフの最小次数は δ(G) と表記し、その中の頂点群の最小次数を意味する。右のグラフでは、最大次数は3、最小次数は0である。正則グラフでは全頂点の次数が等しく、その次数をグラフの次数と呼ぶこともある。 有向グラフでは、頂点に入ってくる辺数を入次数 (indegree)、頂点から出て行く辺数を出次数 (outdegree) と呼ぶ。 握手補題[編集] グラフ の次数の総和は次の公式で表される。 これの証明は double counting という手法(二通りに数え上げる)の例である。グラフ内の辺と頂
![次数 (グラフ理論) - Wikipedia](https://cdn-ak-scissors.b.st-hatena.com/image/square/34265cf011b7d6e4dc25e66a8b989a7834c2a9fc/height=288;version=1;width=512/https%3A%2F%2Fupload.wikimedia.org%2Fwikipedia%2Fcommons%2Fthumb%2F9%2F97%2FUndirectedDegrees.svg%2F1200px-UndirectedDegrees.svg.png)