Пусть А-матрица инцидентности гр-а G(V,E), |V|=n,тогда ( 
)ij-есть число маршрутов длины k от Vi кVj.
Док-во:Использ. индукцию по k: для k=1 маршрут длины 1 явл. ребром гр-а G и результат теоремы вытекает из определения А. Пусть ( 
)ij=αij и пусть Аij=aij,тогда ( )ij=( ∙ A)ij= 
αiq∙ aqj. Пусть результат справедлив для k-1,тогда αiq- число маршрутов длины k-1 от Vi кVq и aqj-число маршрутов длины 1 от Vq кVj, т.о. αiq∙ aqj-это число марш-ов длины k от Vi к Vj,где Vq-предпоследняя верш. ч.т.д.
Следствие.
1)Маршрут от Vi к Vj(i≠j),в гр-фе G сущ-т тогда и только тогда,когда i и j эл-ты матр-ы порядка n 
n,(где n=|V|)≠0. А+ 
+ 
+…+ 
≠0- сама матрица.
2)Если не исп-ть i≠j, то требуемая матрица имеет вид А+ + +…+ + 
≠0.
