Question 1 |
Let G be a simple, finite, undirected graph with vertex set \{v_1,...,v_n\}. Let \Delta (G)
denote the maximum degree of G and let N=\{1,2,...\} denote the set of all possible
colors. Color the vertices of G using the following greedy strategy:
for i = 1,...,n
color(v_i)\leftarrow min\{ j \in N: \text{ no neighbour of } v_i \text{ is colored } j\}
Which of the following statements is/are TRUE?
color(v_i)\leftarrow min\{ j \in N: \text{ no neighbour of } v_i \text{ is colored } j\}
Which of the following statements is/are TRUE?
This procedure results in a proper vertex coloring of G. | |
The number of colors used is at most \Delta (G)+1. | |
The number of colors used is at most \Delta (G). | |
The number of colors used is equal to the chromatic number of G. |
Question 1 Explanation:
Question 2 |
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?
MSQ
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 2 Explanation:
Question 3 |
The following simple undirected graph is referred to as the Peterson graph.

Which of the following statements is/are TRUE?
MSQ

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 3 Explanation:
Question 4 |
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 4 Explanation:
Question 5 |
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 5 Explanation:
There are 5 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.
In question number 10 answer is 3, wrong options are given
Please Check the solution. Answer 7 is correct.
Please correct diagram of question 37. RQ is a directed edge. Thanks.
Image Updated.
Thank you
In Q 39, option B is incorrect, please check. It should be {(u,v), (v,u)}
Option B updated.