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

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

0 votes
0 votes

Draw the graph directly from Adjacency Matrix.

 

The graph is isomorphic to i and iv

–3 votes
–3 votes

We can draw graph directly from Adjacency Matrix.

This Graph will be similar to graph 2.

Hence Answer is (b) only 2.

edited by
Answer:

Related questions

20 votes
20 votes
2 answers
1