How to find no of paths of length 2 in the below graph ?

Question

Determine the number of paths of length $2$ in the following graph

I couldn't get this logic .

Answer 1

Comments

There are only 3 possible paths of length 2, which passes through vertex v1. they are

v4 v1 v2

v3 v1 v2

v4 v1 v3

This can be done by selecting two of the adjacent vertices of v1 , hence C(3,2)

Similarly, it follows for other vertices.

Answer 2

this can be solved using adjacency matrix . and i also can't get the logic. still i have an hard way.

make the adjacency lets call it a . now . $A^2$ means it is stating all paths of from length 2 from any vertex i to vertex j . where i is the any row and j is any column No need to solve full just solve half. as the other half will be stating the same thing. and don't consider the diagonal. now count . it will give 19..

Answer 3

Theorem : Suppose G is a graph with vertices {v1,v2,…,vn} and A is the $n \times n$ adjacency matrix of G. G can be directed or undirected and multiple edges and loops are allowed. Then the (i,j)th entry of $\text{A}^r$ is the number of different paths of length r from $v_i$ to $v_j$ .

Let $\text{A}$ be Adjacency matrix for this graph,

$\text{A}$ = $\begin{bmatrix} 0 &1 &1 &1 &0 &0 \\ 1 &0 &1 &0 & 1 &0 \\ 1& 1 &0 & 1 & 0 &1 \\ 1& 0& 1 &0 & 0 &1 \\ 0&1 &0 &0 &0 &1 \\ 0& 0 &1 &1 &1 &0 \end{bmatrix}$

then for finding paths of length 2 we need to find $\text{A}^2$

$\text{A}^2 =$ $\begin{bmatrix} 3 &1 & 2 & 1 & 1 &2 \\ 1& 3 &1 &2 &0 &2 \\ 2& 1 &4 & 2 & 2 & 1\\ 1 &2 & 2 & 3 & 1 &1 \\ 1& 0 & 2 & 1 &2 &0 \\ 2& 2 &1 &1 & 0 & 3 \end{bmatrix}$

Now add the elements of the upper triangular or lower triangular of $\text{A}^2$

$1 + 2+ 1 + 1 + 2 + 1 + 2 + 0 + 2 + 2 + 2 + 1 + 1 + 1 +  0 = 19$