Beweis
Wir beweisen die Aussage durch Induktion über
, wobei der Induktionsanfang für
unmittelbar aus der Definition der Adjazenzmatrix folgt, da ja die Kanten die einzigen Wege der Länge
sind
(bei
stimmt die Aussage ebenfalls, da es nur die konstanten kantenleeren Wege der Länge
gibt und die
-te Potenz der Matrix als Einheitsmatrix zu interpretieren ist).
Ein Weg der Länge
von
nach
startet mit einer Kante
gefolgt von einem Weg von
nach
der Länge
. 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b625ccb175f39a67df9bfae71d74f2e38f3dd831)