Gráf pont-él illeszkedési mátrixa

Egy G gráf I_G pont-él szomszédsági mátrixa az a mátrix, amely sorai a gráf csúcsaival és oszlopai a gráf éleivel vannak azonosítva és egy u csúcsnak megfelelő sor és egy e élnek megfelelő oszlop találkozásánál lévő pozícióban 1 áll, ha u illeszkedik e-re, amely nem hurokél; 2 áll, ha u illeszkedik e-re, amely hurokél; 0 áll különben, azaz akkor, ha u nem illeszkedik e-re.

Tehát egy gráf szomszédsági mátrixára teljesül, hogy

• elemei 0-k, 1-esek és 2-esek,
• minden oszlop elemeinek összege 2 (két darab 1-est és 0-kat tartalmaz vagy pedig egy darab 2-est és 0-kat tartalmaz).