22 votes

Suppose $\begin{pmatrix}

0&1 &0&0&0&1 \\

1&0&1&0&0&0 \\

0&1&0&1&0&1 \\

0&0&1&0&1&0 \\

0&0&0&1&0&1 \\

1&0&1&0&1&0

\end{pmatrix}$

is the adjacency matrix of an undirected graph with six vertices: that is, the rows and columns are indexed by vertices of the graph, and an entry is $1$ if the corresponding vertices are connected by an edge and is $0$ otherwise; the same order of vertices is used for the rows and columns. Which of the graphs below has the above adjacency matrix?

- Only $(i)$
- Only $(ii)$
- Only $(iii)$
- Only $(iv)$
- $(i)$ and $(ii)$

2

Add each row of matrix by this you will get degree of that vertex so do it for each row then you will get degree sequence of given graph (3 3 2 2 2 2) with this degree sequence check the degree sequence of given option graph you will find

a degree sequence (3 3 2 2 2 2)

b degree sequence (3 3 2 2 2 2)

c. Degree sequence (3 3 3 3 2 2)

D.degree sequence (3 2 2 2 2 2)

C and .D option which will not match with given graph degree sequence

So option e is correct

a degree sequence (3 3 2 2 2 2)

b degree sequence (3 3 2 2 2 2)

c. Degree sequence (3 3 3 3 2 2)

D.degree sequence (3 2 2 2 2 2)

C and .D option which will not match with given graph degree sequence

So option e is correct

27 votes

Best answer

Yes, Option (**E**) must be the right answer.

**Number of edges in the graph:**

Since the graphs are undirected, it can be observed that there will be two $1$'s in the adjacency matrix corresponding to each edge in the graph.

For example, suppose two there is an edge between nodes $A \ \& \ B$, then there will be $1$ in position $[A, B]$ & there will be a $1$ in position $[B,A]$ of the adjacency matrix.

That's why the given adjacency matrix is symmetric.

So the number of edges in the graph must be equal to half the number of $1$'s in the adjacency matrix.

Hence number of edges will be $7$ in the graph.

All the other graphs except (iii), have $7$ edges.So it is clear that the adjacency matrix does not represents graph (iii).

**Isomorphism:**

From the definition of Isomorphic graphs, it can be inferred that,

**Isomorphic graphs must have same (adjacency matrix) representation.**

Thus after eliminating graph (iii) we have to check for isomorphism among graphs (i), (ii) & (iv).

It can clearly be observed that graphs (ii) & (iv) are not isomorphic to each other.

It can also be observed that graph (i) & (ii) are isomorphic(Rotate graph (i) by $90$ degree left/right.

Graph (ii) is looking like a closed envelope in the figure, try to view it like an open envelope, like a trapezium over a rectangle.)

So now it can be inferred that either the adjacency matrix is representing both graphs (i) & (ii) or it is only representing (iv).

**Cycles of length 6 :**

Now from the adjacency matrix it can be observed that there should be a cycle of length $6$ in the graph, since $[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 1] $ are all $1$'s in the matrix.(as $1$ at any position $[x, y]$ represents an edge between $x \ \& \ y$ in the graph).

& both graphs (i) & (ii) have cycles of length $6$, but graph (iv) does not has any cycle of length $6$, it has cycles of length $4 \ \& \ 5$ only.

Thus graph (iv) can not have the above adjacency matrix.

Hence the adjacency matrix represents graphs (i) & (ii).

3

@Anurag-Isomorphism doesn't say that the isomorphic graphs have same adjacency matrix. They will have **similar **but not always same adjacency matrix. However, if you have same adjacency matrix for two graphs then they are definitely isomorphic.

For two isomorphic graphs having adjacency matrix A_{1 }and A_{2}, they are similar and if these two graphs are isomorphic then there should exist a permutation matrix P such that

A_{2}=PA_{1}P^{T}

Reference:

0

I watched the whole video that you provided in above comment. After watching and understanding video, i agree with your thoughts. According to this video, two graphs are isomorphic if and only if there exists such alpha function(see shown in video). If you know the alpha function (means you know the corresponding mapping between vertices of those two graph) then you can easily able to derive that required permutation matrix. Or if you know the permutation matrix and able to derive function alpha.

Reason of statement, that said by Ayush Upadhyaya sir **(if you have same adjacency matrix for two graphs then they are definitely isomorphic**) :- In this case identity matrix will be that required permutation matrix. As permutation matrix exist so, alpha function will also exist.

7 votes

Adjacency matrix represents the graph :

It can be seen that there are only 2 cycles of length 4 and 1 cycle of length 6.

iii) is eliminated as it has a cycle of length 3.

iv) is eliominated as it has a cycle of length 5.

i) and ii) are isomorphic because both have a cycle of length 4 and in that cycle 2 nodes are connected to 1 node each and those 2 nodes are connected using an edge..

So E) is the answer ...

3 votes

this question correspondence to the isomorphism topic, but when to choose hard way if u can do it in easy way. Almost everthing is given. the adajency matrix represents the graph. each row can give u the degree of each vertex. counting 1.

v1=2 v2=2 v3=3 v4=2 v5=2 v6=3.

u only have to search for graph with the above degree. clearly option e.

don't know who upvoted this .

v1=2 v2=2 v3=3 v4=2 v5=2 v6=3.

u only have to search for graph with the above degree. clearly option e.

don't know who upvoted this .

1 vote

Using isomorphism and cycle finding will take a lot of time but an observation can save our precious time during exam.

Option 3 is straightforward out of consideration. Now we are left with 1,2 and 4.In the adjaceny matrix,we can see that vertex 3(row 3) and vertex 6(row 6) have degree=3.

Also,row 3 has entry in 6th column and row 6 has entry in 3rd column,that means the only degree 3 vertices present are directly connected.So option 4 is also ruled out.

Also 1 and 2 are clearly isomorphic.

**Hence option E is absolutely correct.**

0 votes

- Given the adjacency matrix

V1 | V2 | V3 | V4 | V5 | V6 | DEGREE | |
---|---|---|---|---|---|---|---|

V1 | 0 | 1 | 0 | 0 | 0 | 1 | 2 |

V2 | 1 | 0 | 1 | 0 | 0 | 0 | 2 |

V3 | 0 | 1 | 0 | 1 | 0 | 1 | 3 |

V4 | 0 | 0 | 1 | 0 | 1 | 0 | 2 |

V5 | 0 | 0 | 0 | 1 | 0 | 1 | 2 |

V6 | 1 | 0 | 1 | 0 | 1 | 0 | 3 |

We get to know that the degree sequence of the graph is 2 2 2 2 3 3 but the degree sequence of the graph in (iii) is 2 2 3 3 3 3 which clearly does not match so we eliminate this option (iii).

For Graph 4, I begin to label vertices based on the information present in the adjacency matrix.

Soon, you'll get to know that you'll be unable to find a label for vertices in graph (iv).

- V1 is a degree 2 vertex which is adjacent to a degree 2(v2) and degree 3 vertex(6).So, I label it in graph as follows.

- Now Since V2 is adjacent to V1(degree 2) and V3(a degree 3), V3 must be as below.

- Now, as per adjacency matrix, Vertex V3 is adjacent to V6(a degree 3) vertex, which is not possible in above figure. So, we are unable to get a labelling for this graph, so we eliminate this option too!!.

For, graphs (i) and (ii) I am easily able to find a labelling which matches my adjacency matrix.

Graph (1)

Graph 2

Yes, since here two graphs have the same adjacency matrix, they are isomorphic(converse not necessarily true always).So, the answer is **option**** (E).**