1
GATE CSE 2022
Numerical
+1
-0.33

Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is __________.

2
GATE CSE 2022
+1
-0.33

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
A3
B
A3 divided by 2
C
A3 divided by 3
D
A3 divided by 6
3
GATE CSE 2022
MCQ (More than One Correct Answer)
+1
-0.33

Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?

A
The edge with the second smallest weight is always part of any minimum spanning tree of G.
B
One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G.
C
Suppose S $$\subseteq$$ V be such that S $$\ne$$ $$\phi$$ and S $$\ne$$ V. Consider the edge with the minimum weight such that one of its vertices is in S and the other in V \ S. Such an edge will always be part of any minimum spanning tree of G.
D
G can have multiple minimum spanning trees.
4
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.)
GATE CSE Subjects
EXAM MAP
Medical
NEET