edited by
4,163 views
28 votes
28 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?

 

                                     

  1. Only $(i)$
  2. Only $(ii)$
  3. Only $(iii)$
  4. Only $(iv)$ 
  5.  $(i)$ and $(ii)$
edited by

7 Answers

Best answer
28 votes
28 votes

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).

10 votes
10 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 ...

4 votes
4 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 .
1 votes
1 votes

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.

Answer:

Related questions

20 votes
20 votes
2 answers
1