# Math Help - Graph Theory

1. ## Graph Theory

Find the number of paths of length 'n' between any two vertices in K4 if the value of n is 4,5.

(The problem belongs to Discrete Mathematics by Kenneth H Rosen, Sect 8.4 , problem no. 17)

when the value of n is 2 or 3, it can be solved by observation.
Is there a general formulae for the purpose ?

2. ## Re: Graph Theory

You an use the property that powers of the adjacency matrix give the number of paths from one vertex to another. For paths of length 4, for example, we have 21 paths from a vertex to itself and 20 paths from one vertex to another.

3. ## Re: Graph Theory

If you want to find the general answer, then see if you can diagonalize the adjacency matrix. Then you can easily take arbitrary powers of the matrix.

4. ## Re: Graph Theory

thanks a ton..