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