Discrete Mathematics
Set Theory & Algebra
Marks 1Marks 2Marks 5
Linear Algebra
Marks 1Marks 2
Combinatorics
Marks 1Marks 2
Mathematical Logic
Marks 1Marks 2Marks 5
Probability
Marks 1Marks 2
1
GATE CSE 2021 Set 1
MCQ (More than One Correct Answer)
+2
-0

An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.

Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following option is/are correct?

A
If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.
B
Root of T is an articulation point in G if and only if it has 2 or more children.
C
Root of T can never be an articulation point in G.
D
A leaf of T can be an articulation point in G.
2
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+2
-0.67
Let G be a group order 6, and H be a subgroup of G such that 1 < |H| < 6. Which one of the following options is correct?
A
G is always cyclic, but H may not be cyclic.
B
G may not be cyclic, but H is always cyclic.
C
Both G and H are always cyclic.
D
Both G and H may not be cyclic.
3
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+2
-0.67

Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as:

diam(G) = $$\displaystyle\max_{u, x\in V}$$ {the length of shortest path between u and v}

Let M be the adjacency matrix of G.

Define graph G2 on the same set of vertices with adjacency matrix N, where

$$N_{ij} =\left\{ {\begin{array}{*{20}{c}} {1 \ \ \text{if} \ \ {M_{ij}} > 0 \ \ \text{or} \ \ P_{ij} > 0, \ \text{where} \ \ P = {M^2}}\\ {0, \ \ \ \ \ \text{otherwise}} \end{array}} \right.$$

Which one of the following statements is true?

A
diam(G) < diam(G2) â‰¤ diam(G)
B
$$\left\lceil {diam(G)/2} \right\rceil $$ < diam(G2) < diam(G)
C
diam(G2) â‰¤ $$\left\lceil {diam(G)/2} \right\rceil $$
D
diam(G2) = diam(G)
4
GATE CSE 2020
Numerical
+2
-0
Graph G is obtained by adding vertex s to K3,4 and making s adjacent to every vertex of K3,4. The minimum number of colours required to edge-colour G is _____.
Your input ____
GATE CSE Subjects
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization