Question 1 |

Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?

**MSQ**The diagonal entries of A^2 are the degrees of the vertices of the graph. | |

If the graph is connected, then none of the entries of A^{n-1}+I_ncan be zero. | |

If the sum of all the elements of A is at most 2(n-1), then the graph must be acyclic. | |

If there is at least a 1 in each of A's rows and columns, then the graph must be connected. |

Question 1 Explanation:

Question 2 |

The following simple undirected graph is referred to as the Peterson graph.

Which of the following statements is/are TRUE?

Which of the following statements is/are TRUE?

**MSQ**The chromatic number of the graph is 3. | |

The graph has a Hamiltonian path. | |

The following graph is isomorphic to the Peterson graph. | |

The size of the largest independent set of the given graph is 3. (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.) |

Question 2 Explanation:

Question 3 |

Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of

A^3 | |

A^3 divided by 2 | |

A^3 divided by 3 | |

A^3 divided by 6 |

Question 3 Explanation:

Question 4 |

Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is .

72 | |

36 | |

16 | |

48 |

Question 4 Explanation:

Question 5 |

In a directed acyclic graph with a source vertex s, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex v other than s, the quality-score of v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score of s is assumed to be 1.

The sum of the quality-scores of all vertices on the graph shown above is ______

The sum of the quality-scores of all vertices on the graph shown above is ______

929 | |

254 | |

639 | |

879 |

Question 5 Explanation:

Question 6 |

Consider the following directed graph:

Which of the following is/are correct about the graph?

Which of the following is/are correct about the graph?

**[MSQ]**The graph does not have a topological order | |

A depth-first traversal starting at vertex S classifies three directed edges as back edges | |

The graph does not have a strongly connected component | |

For each pair of vertices u and v, there is a directed path from u to v |

Question 6 Explanation:

Question 7 |

An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.

Let T be a DFS tree obtained by doing DFS in a connected undirected graph G.

Which of the following options is/are correct?

Let T be a DFS tree obtained by doing DFS in a connected undirected graph G.

Which of the following options is/are correct?

Root of T can never be an articulation point in G. | |

Root of T is an articulation point in G if and only if it has 2 or more children. | |

A leaf of T can be an articulation point in G. | |

If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u. |

Question 7 Explanation:

Question 8 |

G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4 ,v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7 }. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?

v2v4 | |

v1v4 | |

v4v5 | |

v3v4 |

Question 8 Explanation:

Question 9 |

Graph G is obtained by adding vertex s to K_{3,4} and making s adjacent to every vertex of K_{3,4}. The minimum number of colours required to edge-colour G is _______

4 | |

5 | |

6 | |

7 |

Question 9 Explanation:

Question 10 |

Let G be an undirected complete graph on n vertices, where n\gt2. Then, the number of different Hamiltonian cycles in G is equal to

n! | |

(n-1)! | |

1 | |

\frac{(n-1)!}{2} |

Question 10 Explanation:

There are 10 questions to complete.

Question 6 is of group theory.

Please remove it from here.

Thank You Abhishek Chavle,

We have updated it.

Q 11 and 29 too

Thank You Abhishek Chavle,

We have updated it.

Q32, There is a directed edge between vertices R Q., From R to Q.