1
GATE CSE 2022
MCQ (More than One Correct Answer)
+1
-0.33

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.)
2
GATE CSE 2022
+1
-0.33

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

A
The diagonal entries of A2 are the degrees of the vertices of the graph.
B
If the graph is connected, then none of the entries of An $$-$$ 1 + In can be zero.
C
If the sum of all the elements of A is at most 2(n $$-$$ 1), then the graph must be acyclic.
D
If there is at least a 1 in each of A's rows and columns, then the graph must be connected.
3
GATE CSE 2021 Set 2
+1
-0.33

Let G be a connected undirected weighted graph. Consider the following two statements.

S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.

S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree. Which one of the following options is correct?

A
S1 is false and S2 is true.
B
S1 is true and S2 is false.
C
Both S1 and S2 are true.
D
Both S1 and S2 are false.
4
GATE CSE 2019
+1
-0.33
Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to
A
n!
B
1
C
(n - 1)!
D
$${{\left( {n - 1} \right)!} \over 2}$$
GATE CSE Subjects
EXAM MAP
Medical
NEET