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**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?

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.