GATE CS

Graph theory

Connectivity, matching and colouring

Graph theory studies vertices and edges and the structure they force: how many edges a graph can have, when it is connected and how strongly, when vertices can be paired off (matching), how many colours a proper colouring needs, and when it can be drawn without crossings. The working tools are a handful of counting results (handshaking, tree and planar bounds, chromatic numbers of standard graphs) and a few theorems (Hall, König, Euler, Dirac) applied to a given graph.

14 previous-year questions · 14 solved · 6 practice questions

Terminology, degrees and the handshaking lemma

Convention: a simple graph has no loops and no parallel edges; graphs are simple unless a question says otherwise. A multigraph allows parallel edges (and sometimes loops). In a directed graph each edge is an ordered pair. $n$ is the number of vertices, $m$ the number of edges. The degree of a vertex is the number of edge-ends at it (a loop adds 2). A graph is $k$ -regular if every vertex has degree $k$ . The degree sequence lists the degrees, usually in non-increasing order.

HANDSHAKING LEMMA

v \sum de g (v) = 2 m

Holds for every undirected graph (loops count 2). So the number of odd-degree vertices is always even.

DIRECTED HANDSHAKING

v \sum de g^{+} (v) = v \sum de g^{-} (v) = m

In a directed graph, total out-degree equals total in-degree equals the number of edges.

MOST EDGES IN A SIMPLE GRAPH

m_{m a x} = (2 n) = \frac{n ( n - 1 )}{2}

Attained exactly by the complete graph $K_{n}$ . A $k$ -regular simple graph on $n$ vertices has $m = nk /2$ edges, so it can exist only if $nk$ is even and $0 \leq k \leq n - 1$ .

A walk is a sequence of vertices with consecutive ones adjacent (vertices and edges may repeat). A trail repeats no edge. A path repeats no vertex. A cycle is a closed path of length at least 3 in a simple graph. A degree sequence is graphical if some simple graph has it: the sum must be even, and each degree must be at most $n - 1$ ; beyond this, further tests are needed (for example, $(3, 3, 3, 1)$ has even sum but is not graphical, since three vertices of degree 3 would each be adjacent to all others, forcing the last vertex to have degree 3).

Havel-Hakimi test for a graphical sequence

Sort the sequence $d_{1} \geq d_{2} \geq \dots \geq d_{n}$ .
Delete $d_{1}$ and subtract 1 from each of the next $d_{1}$ entries; the original is graphical exactly when the new sequence is.
Repeat. If a negative entry appears, or $d_{1}$ exceeds the number of remaining entries, the sequence is not graphical; if all entries become 0, it is graphical.
Example: $(3, 3, 3, 1) \to (2, 2, 0) \to (1, - 1)$ , a negative entry, so not graphical.

EXAM TIP

To show a degree sequence is impossible, first check parity of the sum, then try the largest degree: a vertex of degree $n - 1$ is adjacent to everything, so no vertex can have degree 0.

Connectivity, cut vertices, bridges and trees

A graph is connected if there is a path between every pair of vertices; otherwise it splits into components. A cut vertex is a vertex whose removal (with its edges) increases the number of components. A bridge is an edge whose removal increases the number of components; an edge is a bridge exactly when it lies on no cycle. A tree is a connected graph with no cycle; a forest is a graph with no cycle.

EDGES NEEDED FOR $K$ COMPONENTS

m \geq n - k

A graph with $n$ vertices and $k$ components has at least $n - k$ edges; so a connected graph has at least $n - 1$ edges. Equality holds exactly for forests.

MOST EDGES IN A DISCONNECTED SIMPLE GRAPH

m_{m a x} (disconnected) = \frac{( n - 1 ) ( n - 2 )}{2}

Simple graph on $n \geq 2$ vertices with at least 2 components. Attained by $K_{n - 1}$ plus one isolated vertex. With exactly $k$ components the maximum is $(2 n - k + 1)$ .

MINIMUM-DEGREE TEST FOR CONNECTIVITY

δ \geq \frac{n - 1}{2} \Rightarrow G connected

For a simple graph on $n$ vertices with minimum degree $δ$ : any two non-adjacent vertices then have a common neighbour. This is sufficient, not necessary.

VERTEX AND EDGE CONNECTIVITY

κ (G) \leq λ (G) \leq δ (G)

The vertex connectivity $κ (G)$ is the fewest vertices whose removal disconnects $G$ or leaves a single vertex; the edge connectivity $λ (G)$ is the fewest edges whose removal disconnects $G$ . $κ (K_{n}) = λ (K_{n}) = n - 1$ . A connected graph on $n \geq 3$ vertices has a cut vertex exactly when $κ = 1$ , and a connected graph on $n \geq 2$ vertices has a bridge exactly when $λ = 1$ .

Equivalent descriptions of a tree on $n$ vertices

Connected and acyclic.
Connected and has exactly $n - 1$ edges.
Acyclic and has exactly $n - 1$ edges.
There is exactly one path between any two vertices.
Connected, and removing any edge disconnects it (every edge is a bridge).

LEAVES OF A TREE

# leaves = 2 + d e g (v) \geq 3 \sum (de g (v) - 2)

For a tree with $n \geq 2$ vertices. In particular every such tree has at least 2 leaves (vertices of degree 1).

CAYLEY'S FORMULA

τ (K_{n}) = n^{n - 2}

Number of labelled trees on $n$ vertices, which equals the number of spanning trees of $K_{n}$ . Also $τ (K_{p, q}) = p^{q - 1} q^{p - 1}$ and $τ (C_{n}) = n$ .

Matrix-tree idea. Let $L = D - A$ be the Laplacian ( $D$ the diagonal matrix of degrees, $A$ the adjacency matrix). The number of spanning trees of a connected graph equals any cofactor of $L$ : delete one row and the same-numbered column, then take the determinant. The multiplicity of eigenvalue 0 of $L$ equals the number of components.

Special graphs, bipartite graphs, isomorphism and complements

Graph	Vertices	Edges	Notes
$K_{n}$ (complete)	$n$	$\frac{n ( n - 1 )}{2}$	Every pair adjacent; $(n - 1)$ -regular
$C_{n}$ (cycle, $n \geq 3$ )	$n$	$n$	2-regular, connected
$P_{n}$ (path on $n$ vertices)	$n$	$n - 1$	A tree
$K_{p, q}$	$p + q$	$pq$	Complete bipartite
Wheel $W_{n}$ (hub + cycle on $n \geq 3$ rim vertices)	$n + 1$	$2 n$	Hub has degree $n$ , rim vertices degree 3; some questions write $W_{n}$ for the wheel with $n$ vertices in total, so check which
Hypercube $Q_{d}$	$2^{d}$	$d 2^{d - 1}$	$d$ -regular, bipartite
Petersen graph	10	15	3-regular, shortest cycle has length 5, not planar

A graph is bipartite if its vertices split into two sets with every edge between the sets. Test: a graph is bipartite exactly when it has no odd cycle (equivalently, it can be 2-coloured). A bipartite simple graph on $n$ vertices has at most $⌊ n^{2} /4 ⌋$ edges, attained by $K_{⌊ n /2 ⌋, ⌈ n /2 ⌉}$ . Every tree and every even cycle is bipartite.

Isomorphism. Graphs are isomorphic if a bijection of vertices preserves adjacency. To show two graphs are not isomorphic, find an invariant that differs: number of vertices, number of edges, degree sequence, number of cycles of a given length, connectedness, bipartiteness. Equal invariants do not prove isomorphism; for that, exhibit the bijection.

COMPLEMENT EDGE COUNT

m (G) + m (\overline{G}) = (2 n)

For a simple graph $G$ , the complement $\overline{G}$ has the same vertices and exactly the non-edges of $G$ . Degrees satisfy $de g_{\overline{G}} (v) = n - 1 - de g_{G} (v)$ .

SELF-COMPLEMENTARY GRAPHS

G ≅ \overline{G} \Rightarrow m = \frac{n ( n - 1 )}{4}, n \equiv 0 or 1 (mod 4)

Necessary conditions on the order and size of a simple self-complementary graph. Examples: $P_{4}$ (4 vertices, 3 edges) and $C_{5}$ (5 vertices, 5 edges).

For any simple graph, at least one of $G$ and $\overline{G}$ is connected.

Matchings, vertex covers and independent sets

A matching is a set of edges, no two sharing a vertex. A maximum matching has the most edges; a perfect matching covers every vertex (so $n$ is even and it has $n /2$ edges). A vertex cover is a set of vertices touching every edge. An independent set is a set of pairwise non-adjacent vertices. Write $ν$ for the maximum matching size, $β$ for the minimum vertex cover size and $α$ for the maximum independent set size. Always $ν \leq ⌊ n /2 ⌋$ .

INDEPENDENT SET AND VERTEX COVER

α (G) + β (G) = n

Holds for every simple (loopless) graph: a set is independent exactly when its complement is a vertex cover.

KÖNIG'S THEOREM

ν (G) \leq β (G) and ν (G) = β (G) if G is bipartite

Every vertex cover needs a distinct vertex for each matching edge, so $ν \leq β$ always; equality is guaranteed only for bipartite graphs. (The triangle has $ν = 1$ , $β = 2$ .)

HALL'S CONDITION

∣ N (S) ∣ \geq ∣ S ∣ for all S \subseteq X

A bipartite graph with parts $X, Y$ has a matching covering every vertex of $X$ if and only if this holds, where $N (S)$ is the set of neighbours of $S$ . When $∣ X ∣ = ∣ Y ∣$ , this is the condition for a perfect matching.

GALLAI: MATCHING AND EDGE COVER

ν (G) + ρ (G) = n

For a graph with no isolated vertex, the minimum edge cover size $ρ$ plus the maximum matching size $ν$ equals $n$ .

Useful facts about matchings

A $k$ -regular bipartite graph with $k \geq 1$ has a perfect matching (it satisfies Hall's condition).
$K_{n, n}$ has $n!$ perfect matchings; $K_{2 r}$ has $\frac{( 2 r )!}{2 ^{r} r !} = (2 r - 1) (2 r - 3) \dots 3 \cdot 1$ .
$K_{p, q}$ with $1 \leq p \leq q$ has $ν = β = p$ and $α = q$ .
A tree has at most one perfect matching.
The Petersen graph has a perfect matching.

WORKED EXAMPLE

A bipartite graph is $K_{4, 6}$ . Find the size of a maximum matching, a minimum vertex cover and a maximum independent set.

Solution

$K_{4, 6}$ has 10 vertices; each vertex of the smaller side can be matched to a distinct vertex of the larger side, and no matching can use more than the 4 vertices of that side, so $ν = 4$ .
The graph is bipartite, so by König's theorem $β = ν = 4$ (the 4-vertex side is a cover).
By $α + β = n$ , $α = 10 - 4 = 6$ (the 6-vertex side).

Answer: Maximum matching 4, minimum vertex cover 4, maximum independent set 6.

EXAM TIP

To disprove a perfect matching in a bipartite graph, find a set $S$ with $∣ N (S) ∣ < ∣ S ∣$ . If the two sides have different sizes, there is no perfect matching at once.

Colouring and planar graphs

A proper colouring gives adjacent vertices different colours. The chromatic number $χ (G)$ is the fewest colours needed. The clique number $ω (G)$ is the size of the largest complete subgraph, and $χ (G) \geq ω (G)$ . Each colour class is an independent set, so $χ (G) \geq n / α (G)$ .

Graph	Chromatic number
$K_{n}$	$n$
Cycle $C_{n}$ , $n$ even	2
Cycle $C_{n}$ , $n$ odd	3
Any graph with at least one edge that is bipartite (including trees on 2 or more vertices)	2
Edgeless graph	1
Wheel with hub and rim cycle of even length	3
Wheel with hub and rim cycle of odd length	4
Petersen graph	3

GREEDY COLOURING BOUND

χ (G) \leq Δ (G) + 1

For every graph, where $Δ$ is the maximum degree. By Brooks' theorem, a connected graph that is neither a complete graph nor an odd cycle has $χ (G) \leq Δ (G)$ .

CHROMATIC POLYNOMIALS

P (K_{n}, k) P (T, k) P (C_{n}, k) = k (k - 1) \dots (k - n + 1) = k (k - 1)^{n - 1} = (k - 1)^{n} + (- 1)^{n} (k - 1)

$P (G, k)$ is the number of proper colourings of $G$ using at most $k$ colours, with the colours and vertices labelled. $T$ is any tree on $n$ vertices; $C_{n}$ needs $n \geq 3$ . Check: $P (C_{3}, k) = k (k - 1) (k - 2) = P (K_{3}, k)$ . $χ (G)$ is the least $k$ with $P (G, k) > 0$ .

EDGE COLOURING

Δ (G) \leq χ^{'} (G) \leq Δ (G) + 1

The chromatic index $χ^{'} (G)$ is the fewest colours that give edges sharing a vertex different colours. The bounds hold for every simple graph (Vizing). A bipartite graph has $χ^{'} = Δ$ . $χ^{'} (K_{n}) = n - 1$ for even $n$ and $n$ for odd $n$ .

Four-colour theorem: every loopless planar graph has $χ \leq 4$ . A graph is planar if it can be drawn in the plane with no edge crossings; a drawing divides the plane into faces, including the outer face. The degree of a face is the length of the closed walk around its boundary, with a bridge counted twice.

EULER'S FORMULA

V - E + F = 2

For a connected planar graph (drawn without crossings). With $k$ components the right side is $k + 1$ .

EDGE BOUND FOR SIMPLE PLANAR GRAPHS

E \leq 3 V - 6

For a simple planar graph with $V \geq 3$ . If the graph also has no triangle (for example, it is bipartite), $E \leq 2 V - 4$ . Reason: in a simple connected planar graph with $V \geq 3$ , every face has degree at least 3 (at least 4 with no triangle), and $\sum_{f} de g (f) = 2 E$ . More generally, if every cycle has length at least $g$ , then $E \leq \frac{g}{g - 2} (V - 2)$ .

Planarity facts

$K_{5}$ and $K_{3, 3}$ are not planar (for $K_{5}$ : $10 > 3 \cdot 5 - 6 = 9$ ; for $K_{3, 3}$ : $9 > 2 \cdot 6 - 4 = 8$ ).
Kuratowski: a graph is planar exactly when it has no subdivision of $K_{5}$ or $K_{3, 3}$ as a subgraph.
$K_{n}$ is planar exactly when $n \leq 4$ ; $K_{p, q}$ is planar exactly when $min (p, q) \leq 2$ .
Every simple planar graph has a vertex of degree at most 5.
Subgraphs of planar graphs are planar.

WORKED EXAMPLE

A connected planar simple graph is 3-regular with 8 vertices. How many faces does a planar drawing have? Is $E \leq 3 V - 6$ satisfied?

Solution

By handshaking, $2 E = 8 \times 3 = 24$ , so $E = 12$ .
Euler: $F = 2 - V + E = 2 - 8 + 12 = 6$ .
Bound: $3 V - 6 = 18 \geq 12$ , consistent. (The cube graph $Q_{3}$ is such a graph.)

Answer: 6 faces; the bound holds.

Euler and Hamiltonian graphs, and the adjacency matrix

Property	Condition (all edges in one connected piece; isolated vertices ignored)
Euler circuit (closed trail using every edge once), undirected	All degrees even
Euler trail that is not closed, undirected	Exactly 2 vertices of odd degree (the trail starts at one and ends at the other)
Directed Euler circuit	In-degree equals out-degree at every vertex, and the vertices with edges form one strongly connected piece
Directed Euler trail that is not closed	One vertex has out-degree minus in-degree equal to 1 (the start), one has in-degree minus out-degree equal to 1 (the end), all others have in-degree equal to out-degree, and the edges form one connected piece when directions are ignored

A Hamiltonian cycle visits every vertex exactly once and returns to the start; a Hamiltonian path visits every vertex once. Unlike Euler, no simple exact test exists; only sufficient conditions.

DIRAC'S THEOREM

δ (G) \geq \frac{n}{2} \Rightarrow G Hamiltonian

Simple graph with $n \geq 3$ . Ore's generalisation: if $de g (u) + de g (v) \geq n$ for every pair of non-adjacent $u, v$ , then $G$ is Hamiltonian. Both are sufficient only.

HAMILTONIAN CYCLES IN $K_N$

# Hamiltonian cycles of K_{n} = \frac{( n - 1 )!}{2}

For $n \geq 3$ , labelled vertices, counting a cycle and its reverse as the same. $K_{p, q}$ is Hamiltonian exactly when $p = q \geq 2$ , and $K_{n, n}$ ( $n \geq 2$ ) has $\frac{n ! ( n - 1 )!}{2}$ Hamiltonian cycles (1 for $K_{2, 2}$ , 6 for $K_{3, 3}$ ).

A Hamiltonian cycle in a bipartite graph alternates between the parts, so a bipartite graph with parts of unequal size has no Hamiltonian cycle. A Hamiltonian path in a bipartite graph needs part sizes that differ by at most 1, so if they differ by 2 or more there is no Hamiltonian path.

POWERS OF THE ADJACENCY MATRIX

(A^{k})_{ij} = number of walks of length k from i to j

For the adjacency matrix $A$ of a graph (directed or undirected; in a multigraph $A_{ij}$ counts parallel edges, and a loop is entered as 1 in $A_{ii}$ ). Walks may repeat vertices.

What $A$ tells you (simple undirected graph)

Row sums of $A$ are the degrees, so $1^{T} A 1 = 2 m$ .
$tr (A) = 0$ , so the eigenvalues of $A$ sum to 0.
$tr (A^{2}) = 2 m$ .
$tr (A^{3}) = 6 \times (number of triangles)$ .
$A$ is symmetric, so its eigenvalues are real; for a $k$ -regular graph the largest eigenvalue is $k$ .
For a bipartite graph the spectrum is symmetric about 0: if $λ$ is an eigenvalue, so is $- λ$ , with the same multiplicity.

EXAM TIP

Counting edges from $A$ : the number of non-zero entries of a simple undirected graph's $A$ is $2 m$ , not $m$ . Counting trails or paths (rather than walks) cannot be done from $A^{k}$ directly.

PREVIOUS-YEAR QUESTIONS

14 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2024 Set 1 · GATE CSE 2024 Set 2 · GATE CSE 2022 · GATE CSE 2020 · GATE CSE 2018

GATE 2026 CS1 Q.47

GATE 2026 · CS1Q.47 · 2 marks · MSQ

Let $G (V, E)$ be a simple, undirected graph. A vertex cover of $G$ is a subset $V^{'} \subseteq V$ such that for every $(u, v) \in E$ , $u \in V^{'}$ or $v \in V^{'}$ . Let the size of the smallest vertex cover in $G$ be $k$ . Let $S$ be any vertex cover of size $k$ .

For a vertex $v \in V$ , which of the following constraints will always ensure that $v \in S$ ?

(A)
The degree of $v$ is at least $k + 1$
(B)
The vertex $v$ is on a path of length $k + 1$
(C)
The vertex $v$ is on a cycle of length $k + 1$
(D)
The vertex $v$ is a part of a clique of size $k$

Answer and solution

GATE 2026 CS1 Q.47: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS1 Q.47: answer and solution

GATE 2026 CS1 Q.57

GATE 2026 · CS1Q.57 · 2 marks · NAT

Let $G$ be an undirected graph, which is a path on 8 vertices. The number of matchings in $G$ is ______. (answer in integer)

Answer and solution

GATE 2026 CS1 Q.57: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS1 Q.57: answer and solution

GATE 2024 CS1 Q.34

GATE 2024 · CS1Q.34 · 1 mark · NAT

The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is _________

Answer and solution

GATE 2024 CS1 Q.34: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS1 Q.34: answer and solution

GATE 2024 CS1 Q.51

GATE 2024 · CS1Q.51 · 2 marks · MSQ

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$

Answer and solution

GATE 2024 CS1 Q.51: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS1 Q.51: answer and solution

GATE 2024 CS2 Q.17

GATE 2024 · CS2Q.17 · 1 mark · MCQ

Let $A$ be the adjacency matrix of a simple undirected graph $G$ . Suppose $A$ is its own inverse. Which one of the following statements is always TRUE?

(A)
$G$ is a cycle
(B)
$G$ is a perfect matching
(C)
$G$ is a complete graph
(D)
There is no such graph $G$

Answer and solution

GATE 2024 CS2 Q.17: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS2 Q.17: answer and solution

GATE 2024 CS2 Q.60

GATE 2024 · CS2Q.60 · 2 marks · NAT

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 ______.

GATE 2024 CS2 question 60: A graph on 8 vertices drawn at the corners of an octagon, labelled in order around the outline: v0 top-left, v1… — Figure from the GATE 2024 CS2 paper. It is part of the question.

Answer and solution

GATE 2024 CS2 Q.60: answer and solution

GATE 2022 CS Q.30

GATE 2022 · CSQ.30 · 1 mark · NAT

Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.

Answer and solution

GATE 2022 CS Q.30: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.30: answer and solution

GATE 2022 CS Q.37

GATE 2022 · CSQ.37 · 2 marks · MCQ

Consider a simple undirected unweighted graph with at least three vertices. If $A$ is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of

(A)
$A^{3}$
(B)
$A^{3}$ divided by 2
(C)
$A^{3}$ divided by 3
(D)
$A^{3}$ divided by 6

Answer and solution

GATE 2022 CS Q.37: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.37: answer and solution

GATE 2022 CS Q.50

GATE 2022 · CSQ.50 · 2 marks · MSQ

The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are TRUE?

GATE 2022 CS question 50: Top figure: the Peterson graph drawn as an outer regular pentagon with 5 vertices and an inner pentagram (five-pointed… — Figure from the GATE 2022 CS paper. It is part of the question.

(A)
The chromatic number of the graph is 3.
(B)
The graph has a Hamiltonian path.
(C)
The following graph is isomorphic to the Peterson graph. [Figure — a 9-cycle of boundary vertices plus a centre vertex, with six chords as described]
(D)
The size of the largest independent set of the given graph is 3. (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)

Answer and solution

GATE 2022 CS Q.50: answer and solution

GATE 2022 CS Q.52

GATE 2022 · CSQ.52 · 2 marks · MSQ

Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices?

(A)
The diagonal entries of $A^{2}$ are the degrees of the vertices of the graph.
(B)
If the graph is connected, then none of the entries of $A^{n - 1} + I_{n}$ can be zero.
(C)
If the sum of all the elements of $A$ is at most $2 (n - 1)$ , then the graph must be acyclic.
(D)
If there is at least a 1 in each of $A$ 's rows and columns, then the graph must be connected.

Answer and solution

GATE 2022 CS Q.52: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.52: answer and solution

Show the other 4 questions

GATE 2022 CS Q.58

GATE 2022 · CSQ.58 · 2 marks · NAT

Let $G (V, E)$ be a directed graph, where $V = {1, 2, 3, 4, 5}$ is the set of vertices and $E$ is the set of directed edges, as defined by the following adjacency matrix $A$ .

A [i] [j] = {1, 0, 1 \leq j \leq i \leq 5 otherwise

$A [i] [j] = 1$ indicates a directed edge from node $i$ to node $j$ . A directed spanning tree of $G$ , rooted at $r \in V$ , is defined as a subgraph $T$ of $G$ such that the undirected version of $T$ is a tree, and $T$ contains a directed path from $r$ to every other vertex in $V$ . The number of such directed spanning trees rooted at vertex $5$ is ______.

Answer and solution

GATE 2022 CS Q.58: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.58: answer and solution

GATE 2020 CS Q.52

GATE 2020 · CSQ.52 · 2 marks · NAT

Graph $G$ is obtained by adding vertex $s$ to $K_{3, 4}$ and making $s$ adjacent to every vertex of $K_{3, 4}$ . The minimum number of colours required to edge-colour $G$ is ____.

Answer and solution

GATE 2020 CS Q.52: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 CS Q.52: answer and solution

GATE 2018 CS Q.18

GATE 2018 · CSQ.18 · 1 mark · NAT

The chromatic number of the following graph is ________.

GATE 2018 CS question 18: An undirected graph on six vertices a, b, c, d, e, f. — Figure from the GATE 2018 CS paper. It is part of the question.

Answer and solution

GATE 2018 CS Q.18: answer and solution

GATE 2018 CS Q.43

GATE 2018 · CSQ.43 · 2 marks · NAT

Let $G$ be a graph with $100!$ vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2, \dots, 100$ . There is an edge between vertices $u$ and $v$ if and only if the label of $u$ can be obtained by swapping two adjacent numbers in the label of $v$ . Let $y$ denote the degree of a vertex in $G$ , and $z$ denote the number of connected components in $G$ . Then, $y + 10 z =$ ______.

Answer and solution

GATE 2018 CS Q.43: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 CS Q.43: answer and solution

OTHER EXAMS

ISRO: 4 questions

From ISRO's Scientist/Engineer written test: ISRO CS 2025, ISRO CS 2023. They are not counted in the GATE numbers on this page.

ISRO CS 2025 Q.5

ISRO 2025 · CSQ.5 · 1 mark · MCQ

There are 20 shopping malls in a city interconnected by roads. Each shopping mall can be reached through 3 different roads. It is assumed that (i) only one park is planned to be constructed in a region, (ii) roads do not cross each other, (iii) road(s) do not pass through a park. What is the maximum number of parks that can be constructed in the regions enclosed by roads?

(A)
12
(B)
30
(C)
60
(D)
11

Answer and solution

ISRO CS 2025 Q.5: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2025 Q.5: answer and solution

ISRO CS 2025 Q.6

ISRO 2025 · CSQ.6 · 1 mark · MCQ

What is the chromatic number of the graph shown below?

ISRO CS 2025 question 6: Undirected graph on 8 vertices a, b, c, d, e, f, g, h. — Figure from the ISRO CS 2025 paper. It is part of the question.

(A)
3
(B)
4
(C)
5
(D)
6

Answer and solution

ISRO CS 2025 Q.6: answer and solution

ISRO CS 2023 Q.42

ISRO 2023 · CSQ.42 · 1 mark · MCQ

42. Which of the following are true?
(i) In a graph G with 'n' vertices and 'e' edges, sum of degrees of vertices = 2*e
(ii) Eccentricity of a connected graph can never be equal to radius of the graph
(iii) Girth of a graph is the total number of edges in the shortest cycle of the graph
(iv) Graph with equal degree for all vertices is multigraph

(A)
(i), (ii), (iii)
(B)
(ii), (iii), (iv)
(C)
(i), (iii), (iv)
(D)
None of the above

Answer and solution

ISRO CS 2023 Q.42: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2023 Q.42: answer and solution

ISRO CS 2023 Q.43

ISRO 2023 · CSQ.43 · 1 mark · MCQ

If there are five faces and nine vertices in an undirected planar graph, then number of edges is

(A)
14
(B)
16
(C)
12
(D)
None of the above

Answer and solution

ISRO CS 2023 Q.43: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2023 Q.43: answer and solution

PRACTICE

6 questions to test yourself

PRACTICE 11 mark · MCQ

A simple undirected graph has 11 vertices and is not connected. What is the largest possible number of edges it can have?

(A)
45
(B)
55
(C)
36
(D)
50

Answer and solution

Answer: (A)

For a disconnected simple graph the maximum is $\frac{( n - 1 ) ( n - 2 )}{2}$ , from $K_{n - 1}$ plus an isolated vertex.
With $n = 11$ : $\frac{10 \times 9}{2} = 45$ .
55 is $(2 11)$ , which is the complete graph and is connected.

PRACTICE 22 marks · NAT

A connected simple planar graph has 9 vertices, and in a plane drawing every face (including the outer face) has degree exactly 4 (its boundary walk has 4 edges). How many edges does the graph have?

Answer and solution

Answer: $14$

Each face has degree 4, and the sum of face degrees is $2 E$ , so $4 F = 2 E$ and $F = E /2$ .
Euler: $9 - E + E /2 = 2$ , so $E /2 = 7$ and $E = 14$ (with $F = 7$ ).
Check: $14 \leq 2 V - 4 = 14$ , the bound for triangle-free planar graphs, met with equality. $K_{2, 7}$ drawn with 7 four-sided faces is such a graph.

PRACTICE 32 marks · MSQ

The Petersen graph has 10 vertices, is 3-regular and has 15 edges, with shortest cycle of length 5. Which of the following statements are true?

(A)
Its chromatic number is 3.
(B)
It is planar.
(C)
It has a perfect matching.
(D)
It is bipartite.

Answer and solution

Answer: (A), (C)

It contains 5-cycles, so it is not bipartite (D false) and $χ \geq 3$ ; it can be coloured with 3 colours, so $χ = 3$ (A true).
If it were planar, Euler would give $F = 2 - 10 + 15 = 7$ faces, each of degree at least 5, so $5 F \leq 2 E$ , that is $35 \leq 30$ , which is false. So it is not planar (B false); it contains a subdivision of $K_{3, 3}$ .
It has a perfect matching of 5 edges (C true).

PRACTICE 41 mark · NAT

A simple self-complementary graph has 9 vertices. How many edges does it have?

Answer and solution

Answer: $18$

$m (G) + m (\overline{G}) = (2 9) = 36$ .
Since $G ≅ \overline{G}$ , both have the same number of edges, so $m = 36/2 = 18$ (and $9 \equiv 1 (mod 4)$ , as required).

PRACTICE 52 marks · MCQ

A bipartite graph has 12 vertices and a perfect matching. What is the size of its largest independent set?

(A)
4
(B)
5
(C)
6
(D)
7

Answer and solution

Answer: (C)

A perfect matching has $12/2 = 6$ edges, so $ν = 6$ .
For a bipartite graph, König gives $β = ν = 6$ .
Then $α = n - β = 12 - 6 = 6$ .

PRACTICE 61 mark · NAT

How many spanning trees does the complete bipartite graph $K_{2, 3}$ (labelled vertices) have?

Answer and solution

Answer: $12$

Formula: $τ (K_{p, q}) = p^{q - 1} q^{p - 1}$ , so $τ (K_{2, 3}) = 2^{2} \cdot 3^{1} = 12$ .
Check by listing: $K_{2, 3}$ has 6 edges and 5 vertices, so a spanning tree keeps 4 edges, i.e. removes 2 of the 6: $(2 6) = 15$ choices.
The remaining 4 edges fail to form a tree exactly when both edges at one of the three degree-2 vertices are removed (3 choices), since 4 edges on 5 vertices form a tree exactly when connected. So $15 - 3 = 12$ .

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

Graphs: connectivity, matching, colouring

Preparing in Kolkata? IAE Academy's course for GATE CSE.