Adjazenzmatrix/Potenzen/Interpretation/Fakt/Beweis

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