I came across this question in Graph Theory :

A graph on the vertex set \( {1,2,3,n } \) is often denoted by a matrix \(A\) of size \(n\) ,where \(aij\) and \(aji\) are equal to the number of edges with ends \(i\) and \(j\).

What is the \(Combinatorial\) \(Interpretation\) of the entries of \(A2\) ?

Ps: This is posted on behalf of Azhaghu Roopesh M.

## Comments

Sort by:

TopNewestThe \((i,j)\)th entry of \(A^2\) denotes the number of paths of length \(2\) between the vertices \(i\) and \(j\). The proof is easy. Let \(B=A^2\). Then \[B_{ij}=\sum_{k=1}^{n}A_{ik}A_{kj}\] Now let us interpret each of the terms in the above summation. \(A_{ik}\) denote the number of paths of length \(1\) from vertex \(i\) to vertex \(k\). Hence the product \(A_{ik}A_{kj}\) denote the number of paths of length \(2\) from \(i\) to \(j\), passing through \(k\). Thus summing over all intermediate vertices \(k\), we obtain the result. By induction, it also follows that \((i,j)\) th entry of the matrix \(A^{m}\) denote the number of paths of length \(m\) between the vertices \(i\) and \(j\). – Abhishek Sinha · 2 years, 3 months ago

Log in to reply

Btw I am reading Graph Theory from "A course in Combinatorics" , should I continue from there or perhaps you have a better suggestion for me ?

Thanks again . – Azhaghu Roopesh M · 2 years, 3 months ago

Log in to reply

– Abhishek Sinha · 2 years, 3 months ago

I followed Diestel's book on graph theory for basics.Log in to reply

@Pranjal Jain @Matt Enlow @Shashwat Shukla @Raghav Vaidyanathan @Sandeep Bhardwaj Sir, @Vraj Mehta, @Pratik Shastri @Brian Charlesworth Sir\[\] Please do help him. Thanks a lot in advance! \[\] @Azhaghu Roopesh M – Ishan Dasgupta Samarendra · 2 years, 3 months ago

Log in to reply