## Problem1H

Problem1H: A graph on the vertex set ${\left\{ 1,2,\ldots ,n\right\} }$ is often descried by a matrix ${A}$ of size ${n,}$ where ${a_{ij}}$ and ${a_{ji}}$ are equal to the number of edges with ends ${i}$ and ${j}$. What is the combinatorial interpretation of the entries of the matrix ${A^{2}}$?

Solution: Let ${A^{2}=\left( b_{ij}\right) ,}$ then easy to see that ${ b_{ij}}$ means the number of walks of length ${2}$ from vertex ${i}$ to vertiex ${j}.$

Note: Let ${A^{k}=\left( c_{ij}\right) ,}$ then ${c_{ij}}$ means the number of walks of length ${k}$ from ${i}$ to ${j}.$ The edge can be repeated, thus we use ‘walk’ instead of ‘path’. How can we find the number of paths of length ${k}$ from vertex ${i}$ to vertex ${j}$?