次数行列
グラフ G = ( V , E ) {\displaystyle G=(V,E)} with | V | = n {\displaystyle |V|=n} を考えると、 G {\displaystyle G} についての次数行列 D {\displaystyle D} は以下のように定義される n × n {\displaystyle n\times n} 対角行列である。
d i , j := { deg  ( v i ) if i = j 0 otherwise {\displaystyle d_{i,j}:=\left\{{\begin{matrix}\deg(v_{i})&{\mbox{if}}\ i=j\\0&{\mbox{otherwise}}\end{matrix}}\right.}
上式において、頂点の次数 deg  ( v i ) {\displaystyle \deg(v_{i})} は辺がその頂点で終結する回数を合計する。無向グラフでは、これは各ループが頂点の次数を2ずつ増加させることを意味する。有向グラフでは、「次数」という用語は入次数(それぞれの頂点に入ってくる辺の数)または出次数(それぞれの頂点から出ていく辺の数)のどちらをも指す。