GATE CSE 2026 Paper 1 — page 17

Questions 49–51 of 65. Imported answers require review unless explicitly marked reviewed.

Let

be a simple, undirected, edge-weighted graph with unique edge weights.

Which of the following statements about the minimum spanning tree (MST) of

is/are true?

Your answerSelect all correct options. You can choose more than one.

In every cycle

, the edge with the largest weight in

is not in any MST

In every cycle

, the edge with the smallest weight in

is in every MST

For every vertex

, the edge with the largest weight incident on

is not in any MST

For every vertex

, the edge with the smallest weight incident on

is in every MST

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph

as input, where

and

are the discovery time and finishing time, respectively, of the vertex

Suppose that the input directed graph

is a directed acyclic graph (DAG).

For an edge

, which of the following options will NEVER be correct?

Your answerSelect all correct options. You can choose more than one.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let

and

be two languages over a finite alphabet, such that

and

are regular languages. Which of the following statements is/are always true?

Your answerSelect all correct options. You can choose more than one.

is regular

is context-free

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

2026 · Paper 1