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.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## 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\).

Log in to reply

Thanks a lot sir ! I have a long way to go to match up with your skills :D

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 .

Log in to reply

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

Log in to reply