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.

GATE CSE 2022 Discrete Mathematics - Graph Theory Question 6 English

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.

GATE CSE 2022 Discrete Mathematics - Graph Theory Question 6 English Option 3

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
MCQ (Single Correct Answer)
+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
MCQ (Single Correct Answer)
+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
MCQ (Single Correct Answer)
+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
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
CBSE
Class 12