1
GATE CSE 2024 Set 2
Numerical
+2
-0.66

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is ________

2
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$

3
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 ________

4
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.
GATE CSE Subjects
EXAM MAP
Medical
NEET