###### Waste less time on Facebook — follow Brilliant.
×

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.

Note by Ishan Dasgupta Samarendra
2 years, 8 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

The $$(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$$.

- 2 years, 8 months ago

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 .

- 2 years, 8 months ago

I followed Diestel's book on graph theory for basics.

- 2 years, 8 months ago