隣接行列
ここでは(無向グラフについて)、それぞれの辺が行列中の適切なセルに1を加え、それぞれのループが2を加えるという慣習に従う。これによって、隣接行列中のその対応する行または列中の値の和を取るとによって頂点の次数を容易に見付けることが可能である。
無向単純グラフの隣接行列は対称であり、したがって実固有値および直交固有ベクトル基底の完全集合を持つ。グラフの固有値一式はグラフのスペクトルである。通常、固有値を λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n {\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}} と表す。
最大固有値 λ 1 {\displaystyle \lambda _{1}} は最大次数によって上に有界である。これはペロン=フロベニウスの定理の結果として見ることができるが、容易に証明することができる。vを λ 1 {\displaystyle \lambda _{1}} と関連した1つの固有ベクトルとし、xをvが最大の絶対値を持つ成分とする。一般性を失うことなくvxは正と仮定する。なぜならさもなければ、単純に(これも λ 1 {\displaystyle \lambda _{1}} と関連した)固有ベクトル − v {\displaystyle -v} を取ると、
λ v x = ( A v ) x = ∑ y = 1 n A x , y v y ≤ ∑ y = 1 n A x , y v x = v x deg  ( x ) {\displaystyle \lambda v_{x}=(Av)_{x}=\sum _{y=1}^{n}A_{x,y}v_{y}\leq \sum _{y=1}^{n}A_{x,y}v_{x}=v_{x}\deg(x)}
となるためである。