Hogyan lehetne igazolni, hogy ha az A a szomszédsági mátrixa egy véges egyszerű gráfnak, akkor A^2 főátlójában az elemek összege páros?

A bizonyítása egyszerű. Annyit kell tudni, hogy ha A egy ilyen gráf szomszédsági mátrixa, akkor A^n mátrixban az i-edik sor j-edik eleme azt fogja megmutatni, hogy hány n hosszúságú út vezet az i-edik csúcsból a j-edik csúcsba.

Speciálisan A^1 ugye azt mutatja meg, hogy az i. csúcsból hány db 1 hosszúságú út vezet a j. csúcsba, azaz hány él fut közöttük.

Tehát A^2 azt mutatja meg, hogy egyik csúcsból a másikba hány db 2 hosszúságú út vezet.

Mivel a főátlót vesszük, azt nézzük, hogy az egyes csúcsokból hány db 2 hosszúságú út vezet saját magukba. Ez egy egyszerű, véges gráf esetén az adott csúcs fokszámával egyezik meg. (Elmegy egy szomszédba, majd ugyanazon az élen vissza)

Tehát lényegében, ha a főátló elemeit összegezzük, akkor igazából a fokszámokat összegezzük. Azt pedig tudjuk, hogy egy gráfban a fokszámok összege az élek számának kétszerese, tehát páros.

Akkor már álljon kimondva:

"Ha A a G irányított vagy irányítatlan gráf szomszédsági mátrixa, akkor az A^n mátrix rendelkezik egy érdekes értelmezéssel: Az i. sor j. eleme megadja az i csúcsból a j csúcsba menő irányított vagy irányítatlan n hosszúságú séták számát."

[link]

Igen, a többi igaz.