TIFR2015-B-5

1.2k views

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
0
unable to see any graphs
2
fixed now..
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
1

@rajinder singh check your degree sequence for last graph. There are two nodes with degree 3.

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

1 flag
edited by
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 A1 and A2, they are similar and if these two graphs are isomorphic then there should exist a permutation matrix P such that

A2=PA1PT

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.

0
In the adjacency matrix, vertices of degree 3 are connected(i.e. there is a edge between them) but in graph (iv) it is not so. In that way also we can eliminate graph (iv)

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

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

Draw the graph directly from Adjacency Matrix.

The graph is isomorphic to i and iv

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

We can draw graph directly from Adjacency Matrix.

This Graph will be similar to graph 2.

Hence Answer is (b) only 2.

edited

Related questions

1
872 views
Let $K_{n}$ be the complete graph on $n$ vertices labeled $\left\{1, 2,\dots ,n\right\}$ with $m=\frac{n (n - 1)}{2}$ edges. What is the number of spanning trees of $K_{n}$? $\frac{m}{n - 1}$ $m^{n - 1}$ $n^{n - 2}$ $n^{n - 1}$ None of the above.
1 vote
Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given to you by a $0-1$ matrix $A$ of size $n\times n$ as follows. For any $1\leq i,j\leq n,$ the entry $A[i,j]=1$ ... which any two vertices are connected to each other by paths. Give a simple algorithm to find the number of connected components in $G.$ Analyze the time taken by your procedure.
An undirected graph is $\text{connected}$ if, for any two vertices $\{u, v\}$ of the graph, there is a path in the graph starting at $u$ and ending at $v$. A tree is a connected, undirected graph that contains no cycle. A $\text{leaf}$ in a tree is a vertex that has degree ... $u \in V_1$ and v$\in V_2$ or vice versa. Prove that if $G$ is a tree with at least two vertices, then $G$ is bipartite.