Der Einfachheit halber werden hier Gedanken zum Beweis für einfache Graphen (d.h. ohne Schleifen und Mehrfachkanten) mit n Knoten notiert, die Knoten werden von 1 bis n durchnummeriert.
Sei \(G=(V,E)\) ein Graph mit Knotenmenge \(V=\{1,2,...,n\}\) und zugehöriger Kantenmenge \(E\). Die \(n\times n\)- Adjazenzmatrix \(A=(a_{ij})\) mit $$a_{ij}=\begin{cases} 1, \ (i,j)\in E \\ 0, \ (i,j)\notin E \end{cases}$$ beschreibt nun die Adjazenz der Knoten \(i\) und \(j\).
Induktionsanfang. \(k=1\): Es existiert ein Weg der Länge \(1\) zwischen \(i\) und \(j\) \(\Leftrightarrow\) \(\{i,j\}\in E\), bzw., \((i,j)\in E \) \(\Leftrightarrow a_{ij}=1\) als Eintrag von \(A^1=A\). Ansonsten gilt \(a_{ij}=0\) nach Definition der Adjazenzmatrix.
Induktionshypothese. Sei \(k\in \mathbb{N}\) fest und \(B=A^k\) mit \(B=(b_{ij})\). Dann entspricht \(b_{ij}\) der Anzahl der Wege der Länge \(k\) vom Knoten \(i\) zum Knoten \(j\).
Induktionsschritt. \(k\rightarrow k+1\). Sei \(A^{k+1} = (a_{ij}^{'})\) mit \(a_{ij}^{'}=\sum\limits_{r=1}^n a_{ir} \cdot b_{rj}\), wobei \(A^k=B=(b_{ij})\).
Angenommen \(a_{ir}=0\). Dann gilt \(\{i,r\}\notin E\), bzw., \((i,r)\notin E \), also gibt es keine Kante von \(i\) zu einem Zwischenknoten \(r\). Offenbar kann es nun auch keinen Weg von \(i\) nach \(j\) über \(r\) geben, da bereits keine Verbindung von \(i\) zu \(r\) besteht.
Angenommen \(a_{ir}=1\). Dann gilt \(\{i,r\}\in E\), bzw., \((i,r)\in E \), also gibt es eine Kante von \(i\) zu einem Zwischenknoten \(r\).
Nach Induktionshypothese gibt \(b_{rj}\) nun die Anzahl der Wege von \(r\) nach \(j\) der Länge \(k\) an. Mit der Kante \(\{i,r\}\), bzw., \((i,r)\) können die Wege von \(r\) nach \(j\) auf Wege von \(i\) nach \(j\) der Länge \(k+1\) erweitert werden.
Das ergibt also wieder \(b_{rj}\)-Wege. Mit der Summeniteration werden also nun alle Knoten einzeln als Zwischenknoten geprüft. Damit gibt \(a_{ij}^{'}\) die Anzahl der Wege der Länge \(k+1\) vom Knoten \(i\) zum Knoten \(j\) an.
