Matricea de adiacenţă A(n,n) a unui graf G=(X,U) evidenţiază drumurile de lungime 1 între oricare 2 noduri ale grafului.
Pentru a găsi drumurile de lungime 2 între 2 noduri ale unui graf se procedează astfel. Se consideră două noduri $latex x_{i}$ şi $latex x_{j} \in X$. Existenţa unui drum de lungime 2 între ele presupune existenţa unui nod $latex x_{k} \in X$, cu proprietatea că există atât arcul $latex \left ( x_{i},x_{k} \right )$ cât şi arcul $latex \left ( x_{i},x_{k} \right )$. Pentru a vedea dacă acest arc există, se poate lua pe rând fiecare nod al grafului şi verificăm dacă există sau nu ambele arce $latex \left (\left ( x_{i},x_{k} \right ) si \left ( x_{i},x_{k} \right ) \right )$. Aceasta este echivalent cu a verifica dacă în matricea de adiacenţă există vreun indice k astfel încât elementul k al liniei i şi elementul k al coloanei j să fie ambele egale cu 1. Acest lucru este echivalent cu a verifica dacă elementul de pe poziţia (i,j) din $latex A^{2}$ este diferit de 0. Numărul de drumuri de lungime 2 dintre $latex x_{i}$ şi $latex x_{j}$ este dat de valoarea elementului $latex A^{2} \left (i,j \right )$.
Generalizând, numărul de drumuri de lungime k dintre $latex x_{i}$ şi $latex x_{j}$ este dat de valoarea elementului $latex A^{2} \left (i,j \right )$.
Dacă între nodurile $latex x_{i}$ şi $latex x_{j}$ există un drum de lungime >= n atunci el va conţine un număr de noduri mai mare sau egal nu n+1 şi, cum în graf sunt doar n vârfuri, este clar că cel puţin unul, să zicem $latex x_{k}$, va apărea de două ori. Vom avea în acest caz un drum de la $latex x_{i}$ până la prima apariţie a lui $latex x_{k}$, şi un drum de la ultima apariţie a lui $latex x_{k}$ la $latex x_{j}$.Eliminând toate nodurile dintre prima apariţie a lui $latex x_{k}$, şi ultima apariţie a sa vom obţine un drum de la $latex x_{i}$ la $latex x_{j}$, în care $latex x_{k}$ apare o singură dată. Aplicând acest procedeu pentru toate nodurile care apar de mai multe ori pe drum, vom obţine un drum de la $latex x_{i}$ la $latex x_{j}$, în care fiecare nod apare o singură dată (deci un drum elementar), care are evident cel mult n-1 arce. În concluzie, dacă există vreun drum de la $latex x_{i}$ la $latex x_{j}$ atunci există şi un drum elementar şi, deci, va exista o putere a lui A, între $latex A^{1}$ şi $latex A^{n-1}$, în care poziţia (i,j) este diferită de 0. Pentru deciderea existenţei unui drum între oricare două noduri este suficientă, deci, calcularea doar a primelor n-1 puteri ale lui A.
