Egy G egyszerű gráf IG 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 eleme e-nek (u illeszkedik e-rre); 0 áll különben, azaz akkor, ha u nem eleme e-nek.
Tehát egy egyszerű gráf szomszédsági mátrixára teljesül, hogy