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 2023
MCQ (More than One Correct Answer)
+2
-0.67

Let G be a simple, finite, undirected graph with vertex set {$$v_1,...,v_n$$}. Let $$\Delta(G)$$ denote the maximum degree of G and let N = {1, 2, ...} denote the set of all possible colors. Color the vertices of G using the following greedy strategy:

for $$i=1,....,n$$

color($$v_i)$$ $$\leftarrow$$ min{$$j\in N$$ : no neighbour of $$v_i$$ is colored $$j$$}

Which of the following statements is/are TRUE?

A
This procedure results in a proper vertex coloring of G.
B
The number of colors used is at most $$\Delta(G)+1$$.
C
The number of colors used is at most $$\Delta(G)$$
D
The number of colors used is equal to the chromatic number of G.
4
GATE CSE 2023
Numerical
+2
-0.67

Let $$U = \{ 1,2,3\} $$. Let 2$$^U$$ denote the powerset of U. Consider an undirected graph G whose vertex set is 2$$^U$$. For any $$A,B \in {2^U},(A,B)$$ is an edge in G if and only if (i) $$A \ne B$$, and (ii) either $$A \supseteq B$$ or $$B \supseteq A$$. For any vertex A in G, the set of all possible orderings in which the vertices of G can be visited in a Breadth First Search (BFS) starting from A is denoted by B(A).

If $$\phi$$ denotes the empty set, then the cardinality of B($$\phi$$) is ___________

Your input ____
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12