Crack
GATE
C
G
Topic
Graphs
Engineering Mathematics
0
/ 20 done
Questions per paper
All
MCQ
MSQ
NAT
2015 to 2026. Point at a year to read it.
0
1
2
3
4
5
2015
2019
2021
2023
2025
2026
Show as a table
Year
All
MCQ
MSQ
NAT
2015
1.3
1
0
0.3
2018
0
0
0
0
2019
0
0
0
0
2020
1
0
0
1
2021
1
0.5
0
0.5
2022
5
1
2
2
2023
2
0
1
1
2024
2
0.5
1
0.5
2025
0
0
0
0
2026
1
0
0.5
0.5
1
CS 2026 Set 1 · 2 marks · MSQ · Moderate
An undirected, unweighted, simple graph
G
(
V
,
E
)
G(V,E)
G
(
V
,
E
)
is said to be 2-colorable if there exists a function
c
:
V
→
{
0
,
1
}
c: V \to \{0, 1\}
c
:
V
→
{
0
,
1
}
such that for every
(
u
,
v
)
∈
E
(u, v) \in E
(
u
,
v
)
∈
E
,
c
(
u
)
≠
c
(
v
)
c(u) \neq c(v)
c
(
u
)
=
c
(
v
)
.
2
CS 2026 Set 1 · 2 marks · NAT · Moderate
Let
G
G
G
be an undirected graph, which is a path on 8 vertices. The number of matchings in
G
G
G
is ________. (answer in integer)
3
CS 2024 Set 1 · 2 marks · MSQ · Moderate
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let
G
G
G
be any graph with
n
n
n
vertices and chromatic number
k
k
k
. Which of the following statements is/are always TRUE?
4
CS 2024 Set 2 · 1 mark · MCQ · Moderate
Let
A
A
A
be the adjacency matrix of a simple undirected graph
G
G
G
. Suppose
A
A
A
is its own inverse. Which one of the following statements is always TRUE?
5
CS 2024 Set 2 · 2 marks · MSQ · Hard
Let
G
G
G
be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in
G
G
G
has even weight. Which of the following statements is/are TRUE for every such graph
G
G
G
?
6
CS 2024 Set 2 · 2 marks · NAT · Easy
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 ____\n
7
CS 2023 · 2 marks · MSQ · Moderate
Let
G
G
G
be a simple, finite, undirected graph with vertex set
{
v
1
,
…
,
v
n
}
\{v_1,\ldots,v_n\}
{
v
1
,
…
,
v
n
}
. Let
Δ
(
G
)
\Delta(G)
Δ
(
G
)
denote the maximum degree of
G
G
G
and let
N
=
{
1
,
2
,
…
}
\mathbb{N}=\{1,2,\ldots\}
N
=
{
1
,
2
,
…
}
denote the set of all possible colors. Color the vertices of
G
G
G
using the following greedy strategy:
8
CS 2023 · 2 marks · NAT · Hard
Let
U
=
{
1
,
2
,
3
}
U=\{1,2,3\}
U
=
{
1
,
2
,
3
}
. Let
2
U
2^U
2
U
denote the powerset of
U
U
U
. Consider an undirected graph
G
G
G
whose vertex set is
2
U
2^U
2
U
. For any
A
,
B
∈
2
U
A,B\in 2^U
A
,
B
∈
2
U
,
(
A
,
B
)
(A,B)
(
A
,
B
)
is an edge in
G
G
G
if and only if (i)
A
≠
B
A\ne B
A
=
B
, and (ii) either
A
⊆
B
A\subseteq B
A
⊆
B
or
B
⊆
A
B\subseteq A
B
⊆
A
. For any vertex
A
A
A
in
G
G
G
, the set of all possible orderings in which the vertices of
G
G
G
can be visited in a Breadth First Search (BFS) starting from
A
A
A
is denoted by
B
(
A
)
B(A)
B
(
A
)
.
9
CS 2022 · 1 mark · NAT · Easy
Consider a simple undirected graph of
10
10
10
vertices. If the graph is disconnected, then the maximum number of edges it can have is ____.
10
CS 2022 · 2 marks · MCQ · Easy
Consider a simple undirected unweighted graph with at least three vertices. If
A
A
A
is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of
11
CS 2022 · 2 marks · MSQ · Hard
The following simple undirected graph is referred to as the Peterson graph.
12
CS 2022 · 2 marks · MSQ · Moderate
Which of the properties hold for the adjacency matrix
A
A
A
of a simple undirected unweighted graph having
n
n
n
vertices?
13
CS 2022 · 2 marks · NAT · Moderate
Let
G
(
V
,
E
)
G(V, E)
G
(
V
,
E
)
be a directed graph, where
V
=
{
1
,
2
,
3
,
4
,
5
}
V = \{1, 2, 3, 4, 5\}
V
=
{
1
,
2
,
3
,
4
,
5
}
is the set of vertices and
E
E
E
is the set of directed edges, as defined by the following adjacency matrix
A
A
A
.
14
CS 2021 Set 1 · 1 mark · NAT · Easy
In an undirected connected planar graph
G
G
G
, there are eight vertices and five faces. The number of edges in
G
G
G
is ____.
15
CS 2021 Set 1 · 2 marks · MCQ · Hard
Let
G
=
(
V
,
E
)
G = (V, E)
G
=
(
V
,
E
)
be an undirected unweighted connected graph. The
diameter
of
G
G
G
is defined as:
d
i
a
m
(
G
)
=
max
u
,
v
∈
V
{
the length of shortest path between
u
and
v
}
\mathrm{diam}(G) = \max_{u, v \in V} \{\text{the length of shortest path between } u \text{ and } v\}
diam
(
G
)
=
max
u
,
v
∈
V
{
the length of shortest path between
u
and
v
}
Let
M
M
M
be the adjacency matrix of
G
G
G
. Define graph
G
2
G_2
G
2
on the same set of vertices with adjacency matrix
N
N
N
, where
N
i
j
=
{
1
if
M
i
j
>
0
or
P
i
j
>
0
,
where
P
=
M
2
0
otherwise
N_{ij} = \begin{cases} 1 & \text{if } M_{ij} > 0 \text{ or } P_{ij} > 0, \text{ where } P = M^2 \\ 0 & \text{otherwise} \end{cases}
N
ij
=
{
1
0
if
M
ij
>
0
or
P
ij
>
0
,
where
P
=
M
2
otherwise
Which one of the following statements is true?
16
CS 2020 · 2 marks · NAT · Moderate
Graph
G
G
G
is obtained by adding vertex
s
s
s
to
K
3
,
4
K_{3,4}
K
3
,
4
and making
s
s
s
adjacent to every vertex of
K
3
,
4
K_{3,4}
K
3
,
4
. The minimum number of colours required to edge-colour
G
G
G
is ____.
17
CS 2015 Set 1 · 2 marks · NAT · Moderate
Let
G
G
G
be a connected planar graph with
10
10
10
vertices. If the number of edges on each face is three, then the number of edges in
G
G
G
is _______.
18
CS 2015 Set 2 · 2 marks · MCQ · Moderate
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on
n
n
n
vertices,
n
n
n
is
19
CS 2015 Set 2 · 2 marks · MCQ · Moderate
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?
20
CS 2015 Set 3 · 2 marks · MCQ · Moderate
Consider three software items:
P
r
o
g
r
a
m
−
X
\mathrm{Program-}X
Program
−
X
, Control Flow Diagram of
P
r
o
g
r
a
m
−
Y
\mathrm{Program-}Y
Program
−
Y
and Control Flow Diagram of
P
r
o
g
r
a
m
−
Z
\mathrm{Program-}Z
Program
−
Z
as shown below