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