GATE CSE 2022 | Graph Theory Question 1 | Discrete Mathematics

GATE CSE 2022

MCQ (More than One Correct Answer)

-0.33

Which of the following statements is/are TRUE for a group G?

If for all x, y $$\in$$ G, (xy)² = x²y², then G is commutative.

If for all X $$\in$$ G, x² = 1, then G is commutative. Here, 1 is the identity element of G.

If the order of G is 2, then G is commutative.

If G is commutative, then a subgroup of G need not be commutative.

GATE CSE 2022

Numerical

-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 __________.

Your input ____

GATE CSE 2022

MCQ (Single Correct Answer)

-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³

A³ divided by 2

A³ divided by 3

A³ divided by 6

GATE CSE 2022

MCQ (More than One Correct Answer)

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

The edge with the second smallest weight is always part of any minimum spanning tree of G.

One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G.

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.

G can have multiple minimum spanning trees.