1
GATE CSE 2024 Set 1
MCQ (More than One Correct Answer)
+2
-0.66

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$. Which of the following statements is/are always TRUE?

A

$G$ contains a complete subgraph with $k$ vertices

B

$G$ contains an independent set of size at least $n/k$

C

$G$ contains at least $k(k-1)/2$ edges

D

$G$ contains a vertex of degree at least $k$

2
GATE CSE 2024 Set 1
Numerical
+2
-0.66

The number of edges present in the forest generated by the DFS traversal of an undirected graph G with 100 vertices is 40. The number of connected components in G is ________

Your input ____
3
GATE CSE 2021 Set 1
MCQ (More than One Correct Answer)
+2
-0.67

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.
4
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.
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
Defence
NDA
CBSE
Class 12