Wir beweisen die Aussage durch Induktion über ${\displaystyle {}\ell }$, wobei der Induktionsanfang für ${\displaystyle {}\ell =1}$ unmittelbar aus der Definition der Adjazenzmatrix folgt, da ja die Kanten die einzigen Wege der Länge ${\displaystyle {}1}$ sind (bei ${\displaystyle {}\ell =0}$ stimmt die Aussage ebenfalls, da es nur die konstanten kantenleeren Wege der Länge ${\displaystyle {}0}$ gibt und die ${\displaystyle {}0}$-te Potenz der Matrix als Einheitsmatrix zu interpretieren ist). Ein Weg der Länge ${\displaystyle {}\ell +1}$ von ${\displaystyle {}u}$ nach ${\displaystyle {}v}$ startet mit einer Kante ${\displaystyle {}\{u,w\}}$ gefolgt von einem Weg von ${\displaystyle {}w}$ nach ${\displaystyle {}v}$ der Länge ${\displaystyle {}\ell }$. Es gilt also unter Verwendung der Induktionsvoraussetzung

${\displaystyle {}{\begin{aligned}{\#\left({\text{ Weg von }}u{\text{ nach }}v{\text{ der Länge }}\ell +1\}\right)}&=\sum _{\{u,w\}\in E}{\#\left({\text{ Weg von }}w{\text{ nach }}v{\text{ der Länge }}\ell \}\right)}\\&=\sum _{\{u,w\}\in E}{\left(A^{\ell }\right)}_{(w,v)}\\&=\sum _{w\in V}A_{(u,w)}{\left(A^{\ell }\right)}_{(w,v)}\\&={\left(A\cdot A^{\ell }\right)}_{(u,v)}\\&={\left(A^{\ell +1}\right)}_{(u,v)}\end{aligned}}}$