Exams › GATE › Technical

The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are TRUE? (A) The chromatic number of the graph is 3. (B) The graph has a Hamiltonian path. (C) The following graph is isomorphic to the Peterson graph. (D) 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.)

1. (A) The chromatic number of the graph is 3.
2. (B) The graph has a Hamiltonian path.
3. (C) The following graph is isomorphic to the Peterson graph.
4. (D) 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.)

Correct answer: (A) The chromatic number of the graph is 3.

Solution

The chromatic number of the Petersen graph is indeed 3 because it requires three colors to color the vertices such that no two adjacent vertices share the same color, which is a characteristic of this specific graph.

Related GATE Technical questions

• Which one of the following regular expressions correctly represents the language of the finite automaton given below?
• Which one of the following statements is TRUE?
• In a relational data model, which one of the following statements is TRUE?
• Consider the problem of reversing a singly linked list. To take an example, given the linked list below, head -> a -> b -> c -> d -> e -> NULL, the reversed linked list should look like head -> e -> d -> c -> b -> a -> NULL. Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?
• Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h1 and h2. Further suppose our hashing scheme uses h1 for the odd keys and h2 for the even keys. What is the expected number of keys in a slot?
• Which one of the following facilitates transfer of bulk data from hard disk to main memory with the highest throughput?

⚔️ Practice GATE Technical free + battle 1v1 →