Egy G egyszerű gráf AG szomszédsági mátrixa az a mátrix, amely sorai és oszlopai is a gráf csúcsaival vannak azonosítva és egy u csúcsnak megfelelő sor és egy v csúcsnak megfelelő oszlop találkozásánál lévő pozícióban 1 áll, ha u és v szomszédos; 0 áll, különben, azaz akkor, ha a két csúcs nem szomszédos.
Tehát egy egyszerű gráf szomszédsági mátrixára teljesül, hogy