Gráf illeszkedési mátrixa

Sorai a csúcsokat, oszlopai az éleket jelölik. Egy elem érteke 1, ha az adott csúcs az adott él kezdőpontja, -1, ha a végpontja, egyébként 0.

c komponensből álló n csúcsú gráf illeszkedési mátrixának rangja n-c.

Ha G nem összefüggő, B_G átrendezhető blokkdiagonális szerkezetűvé, azaz négyzetekben van 0-tól különböző érték, és ezek a négyzetek az átlóra illeszkednek. Ilyenkor a mátrix rangja a blokkok rangjának összege.

Összefüggő gráf esetén a gráf egy feszítőfájához tartozó n-1 oszlop lineárisan független.

Egy összefüggő, hurokélmentes n csúcsú gráf illeszkedési mátrixának n-1 sora lineárisan független, ha a nekik megfelelő élek a gráf egy feszítőfájának élei.