Egy G hurokél-nélküli 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 m áll, ha m darab olyan él van a gráfban, amely végponthalmaza {u,v}
Tehát egy hurokél-nélküli gráf szomszédsági mátrixára teljesül, hogy
Ha egy hurokél-nélküli gráf nem egyszerű, akkor elemi között van 1-nél nagyobb is.