凸多面体に於いて、頂点の数をV、辺の数をE、面の数をF、とすると、
V-E+F=2
という関係が成り立つ。
この関係をオイラーの多面体公式、またはオイラーの多面体定理というんだそう。平面グラフに於いても、グラフ全体を取り囲んでいる外側の領域も面の一つと考えれば、同じ関係が成り立つ。
今、頂点の数がV、辺の数がEのグラフGに対し、位数2の体上のV行E列の行列Mを、各頂点を行に、各辺を列に対応させ、頂点が辺の端点となっている時、その頂点と辺に対応する成分を1（但し、ループの辺の端点になっている場合は例外的に0とする）とし、それ以外は0である時、行列MをグラフGの頂点辺行列と呼ぶ事にする。
Mは、ともに位数2の体上の、E次元ベクトル空間からV次元ベクトル空間への準同型写像であり、したがって核ker(M)が定義される。ker(M)の元は、G上の全てのサイクルとそれら全ての組み合わせからなる、E次元ベクトル空間の部分空間となる。
Gが球面グラフ（多面体）であれば、ker(M)の次元dim(ker(M))は、Gの面の数をFとすると、(F-1)に一致する。なぜならば、面はGのサイクルであり、一つの面は残りの全ての面の和で表されるが、その場合を除けば他の面の和で表す事ができず、その一方でG上の任意のサイクルの組は、これら(F-1)個の面の和でいかようにも表す事ができる。
これを、球面グラフに限らず、一般のグラフに拡張できる事に気付いた。すなわち、一般のグラフGに於いて、コンポーネントの数をC、頂点の数をV、辺の数をE、頂点辺行列をM、とするとき、
dim(ker(M))=C-V+E
が成り立つ。
証明は、新しいサイクルができる場合に核の次元が一つ増え、決して減らない事に注意すれば、グラフから辺を一つずつ取り除いて頂点のみとし、今度はその逆順に辺を付け加えていって、コンポーネントの数と次元の変化を比較すれば良い。これはGに多重辺やループがあっても成立する。
