La matrice d'adjacence est la matrice où le coefficient à la ligne i et la colonne j représente le nombre d'arêtes reliant le sommet i au sommet j
En élevant la matrice d'adjacence à la puissance k, c'est-à-dire en procédant à la multiplication de k fois la matrice d'adjacence, les coefficients de la matrice finale s'interprètent comme le nombre de chemins reliant les sommets i et j, distincts et longs de k arêtes
La matrice d'adjacence existe, que le graphe soit orienté ou non. Si le graphe n'est pas orienté, la matrice d'adjacence a la propriété d'être symétrique, puisqu'une arête reliant un sommet i au sommet j dans ce sens, relie réciproquement le sommet j au sommet i dans ce sens.