Question

# Let A = v1 v2 v3 v1 2 8 16 v2 8 0 4 v3 16...

Let A =

 v1 v2 v3 v1 2 8 16 v2 8 0 4 v3 16 4 1

be the ADJACENCY MATRIX for an undirected graph G. Solve the following:

1) Determine the number of edges of G

2) Determine the total degree of G

3) Determine the degree of each vertex of G

4) Determine the number of different walks of length 2 from vertex v3 to v1

5) Does G have an Euler circuit? Explain

1) Number of edges in G= no. of loops + number of edges between two different vertices

Number of loops = 2+1 =3

Number of edges between vertices = #edges between v1-v2 + #edges between v1-v3 + #edges between v2-v3 = 8+16+4=28

Thus number of edges in G = 31

2) Total degree of G = sum of degree of each vertices = degree of v1 + degree of v2 + degree of v3 = 26 + 12 + 21 = 59

3) Degree of each vertex = number of edges incident from each vertex. Thus:

degree of v1 = 26

degree of v2 = 12

degree of v3 = 21

4) Number of different walks of length from v3 to v1:

case(i) v3-v1-v1 = number of walks = 16*2 = 32

case(ii) v3-v3-v1 = 1*16 =16

case(iii) v3-v2-v1 = 4*8 = 32

thus total number of different walks = 80

5) Yes, the graph is Eulerian as each vertex is connected to other vertices.

#### Earn Coins

Coins can be redeemed for fabulous gifts.