Previously , i had shown the property of graphs used to identify nth degree connections. Here i show a proof of the same

An important point to note here is that if A*B=C and A,B,C are matrices , the C(ij) = ith row of A * jth column of B.

Hence , if adjacency Matrix of a graph is A, A

As in a previous post ,ij-th element of A

A

Hence (ij)th element of A

Here, N=stands for total number of nodes (1 to N) , k any arbitrary node from 1 to N, i the ith node and j the jth node .

Let us now generalize the above expression for (ij)th element of A

rewriting (2) as

the summation nested at the innermost , has already been shown in (1);solving it recursively for each nested summation using (1) itself we arrive at the number of links of length 'n' from for i-j.

yes , it is intuitive :)

An important point to note here is that if A*B=C and A,B,C are matrices , the C(ij) = ith row of A * jth column of B.

Hence , if adjacency Matrix of a graph is A, A

^{n }= A*A*A*....*A .If A is un-directed it is symmetric.As in a previous post ,ij-th element of A

^{n }is the number of links of length n from ith node to the jth node.A

^{n }= A*A*A*....*AHence (ij)th element of A

^{2 }can be expressed as**∑a(i,k)*a(k,j)***where k = 1,2...,N*----(1)Here, N=stands for total number of nodes (1 to N) , k any arbitrary node from 1 to N, i the ith node and j the jth node .

Let us now generalize the above expression for (ij)th element of A

^{n }as**∑****∑****∑****∑****....****∑ (****a(i,k1)*a(k1,k2)*****a(k2,k3)*****a(k3,k4)*.....****a(k(n-1),j)***where k1,k2,k3,k4....k(n-1) each**= 1,2....,N*----(2)rewriting (2) as

**∑****∑****∑ ...****∑****a(k(n-1),j)*...****a(k3,k4)*****a(k2,k3)*****∑****(****a(i,k1)*a(k1,k2)**

the summation nested at the innermost , has already been shown in (1);solving it recursively for each nested summation using (1) itself we arrive at the number of links of length 'n' from for i-j.

yes , it is intuitive :)

^{}