Graph Theory: GATE CS previous year questions (Engineering Mathematics)

Hide the 1 question not in the current syllabus

GATE CS 2026 Set 1MSQ2 marksMedium (estimate)
GATE CS 2026 Set 1, Q.47
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...
Graph Theory
GATE CS 2026 Set 2MCQ2 marksMedium (estimate)
GATE CS 2026 Set 2, Q.36
Consider a complete graph $K_{n}$ with $n$ vertices ( $n > 4$ ). Note that multiple spanning trees can be constructed over $K_{n}$ . Each of these spanning trees is represented as a se...
Graph Theory
GATE CS 2024 Set 1NAT1 markEasy (estimate)
GATE CS 2024 Set 1, Q.34
The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is _________
Graph Theory
GATE CS 2024 Set 1MSQ2 marksMedium (estimate)
GATE CS 2024 Set 1, Q.51
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$ . Whic...
Graph Theory
GATE CS 2024 Set 2MCQ1 markMedium (estimate)
GATE CS 2024 Set 2, Q.17
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?
Graph Theory · Linear Algebra
GATE CS 2024 Set 2MSQ2 marksHard (estimate)
GATE CS 2024 Set 2, Q.51
Let $G$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $G$ has even weight. Which of the following state...
Graph Theory · Minimum Spanning Trees
GATE CS 2024 Set 2NAT2 marksMedium (estimate)
GATE CS 2024 Set 2, Q.59
The number of distinct minimum-weight spanning trees of the following graph is _________ Undirected weighted graph with 7 vertices a, b, c, d, e, f, g and 12 edges: (a,b)=1, (a,...
Minimum Spanning Trees · Graph Theory
GATE CS 2024 Set 2NAT2 marksMedium (estimate)
GATE CS 2024 Set 2, Q.60
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 _________ An 8-vertex 4-...
Graph Theory
GATE CS 2023NAT1 markMedium (estimate)
GATE CS 2023, Q.30
Let $A$ be the adjacency matrix of the graph with vertices ${1, 2, 3, 4, 5}$ . Undirected graph with 5 vertices {1, 2, 3, 4, 5}, edges (1,2), (2,3), (2,4), (3,5), (4,5), and se...
Linear Algebra · Graph Theory
GATE CS 2023MSQ2 marksMedium (estimate)
GATE CS 2023, Q.55
Let $G$ be a simple, finite, undirected graph with vertex set ${v_{1}, \dots, v_{n}}$ . Let $Δ (G)$ denote the maximum degree of $G$ and let $N = {1, 2, \dots}$ deno...
Graph Theory · Greedy Algorithms
GATE CS 2023NAT2 marksMedium (estimate)
GATE CS 2023, Q.56
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 an...
Graph Theory · Graph Traversals, Topological Sort and Connectivity
GATE CS 2022NAT1 markEasy (estimate)
GATE CS 2022, Q.30
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.
Graph Theory
GATE CS 2022MCQ2 marksEasy (estimate)
GATE CS 2022, Q.37
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 t...
Graph Theory
GATE CS 2022MSQ2 marksHard (estimate)
GATE CS 2022, Q.50
The following simple undirected graph is referred to as the Peterson graph. The Petersen graph drawn with an outer 5-cycle, an inner 5-pointed star, and 5 radial spokes connecti...
Graph Theory
GATE CS 2022MSQ2 marksMedium (estimate)
GATE CS 2022, Q.52
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?
Graph Theory
GATE CS 2022NAT2 marksMedium (estimate)
GATE CS 2022, Q.58
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.…
Graph Theory
GATE CS 2021 Set 1NAT1 markEasy (estimate)
GATE CS 2021 Set 1, Q.26 (CS Q.16)
In an undirected connected planar graph $G$ , there are eight vertices and five faces. The number of edges in $G$ is __________
Graph Theory
GATE CS 2021 Set 1MCQ2 marksMedium (estimate)
GATE CS 2021 Set 1, Q.46 (CS Q.36)
Let $G = (V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as…
Graph Theory
GATE CS 2020NAT2 marksHard (estimate)
GATE CS 2020, Q.62 (CS Q.52)
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 _______.
Graph Theory
GATE CS 2019MCQ1 markEasy (estimate)
GATE CS 2019, Q.22 (CS Q.12)
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$ . Then, the number of different Hamiltonian cycles in $G$ is equal to
Graph Theory
GATE CS 2018NAT1 markEasy (estimate)
GATE CS 2018, Q.28 (CS Q.18)
The chromatic number of the following graph is _______. 6-vertex undirected graph consisting of an outer 4-cycle and two inner vertices with diagonal cross-connections to find c...
Graph Theory
GATE CS 2018NAT2 marksMedium (estimate)
GATE CS 2018, Q.53 (CS Q.43)
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...
Graph Theory
GATE CS 2017 Set 1NAT1 markEasy (estimate)
GATE CS 2017 Set 1, Q.20 (CS Q.20)
Let $T$ be a tree with 10 vertices. The sum of the degrees of all the vertices in $T$ is ______.
Graph Theory
GATE CS 2017 Set 1MCQ2 marksEasy (estimate)
GATE CS 2017 Set 1, Q.26 (CS Q.26)
Let $G = (V, E)$ be any connected undirected edge-weighted graph. The weights of the edges in $E$ are positive and distinct. Consider the following statements: (I) Minimum Spann...
Greedy Algorithms · Graph Theory
GATE CS 2017 Set 2NAT1 markEasy (estimate)
GATE CS 2017 Set 2, Q.23 (CS Q.23)
$G$ is an undirected graph with $n$ vertices and 25 edges such that each vertex of $G$ has degree at least 3. Then the maximum possible value of $n$ is
Graph Theory
GATE CS 2016 Set 2NAT1 markEasy (estimate)
GATE CS 2016 Set 2, Q.13 (CS Q.3)
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
Graph Theory
GATE CS 2016 Set 2MCQ2 marksMedium (estimate)
GATE CS 2016 Set 2, Q.38 (CS Q.28)
Consider a set $U$ of 23 different compounds in a Chemistry lab. There is a subset $S$ of $U$ of 9 compounds, each of which reacts with exactly 3 compounds of $U$ . Consider the...
Graph Theory
GATE CS 2015 Set 1NAT2 marksEasy (estimate)
GATE CS 2015 Set 1, Q.64 (CS Q.54)
Let $G$ be a connected planar graph with $10$ vertices. If the number of edges on each face is three, then the number of edges in $G$ is _____.
Graph Theory
GATE CS 2015 Set 2MCQ2 marksEasy (estimate)
GATE CS 2015 Set 2, Q.38 (CS Q.28)
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $n$ vertices, $n$ is
Graph Theory
GATE CS 2015 Set 2MCQ2 marksEasy (estimate)
GATE CS 2015 Set 2, Q.60 (CS Q.50)
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?
Graph Theory
GATE CS 2015 Set 3MCQ2 marksMedium (estimate)Not in current syllabus
GATE CS 2015 Set 3, Q.65 (CS Q.55)
Consider three software items: Program-X, Control Flow Diagram of Program-Y and Control Flow Diagram of Program-Z as shown below. Program-X: sumcal(int maxint, int value) {...
Graph Theory
GATE CS 2014 Set 1NAT2 marksMedium (estimate)
GATE CS 2014 Set 1, Q.61 (CS Q.51)
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is ${(i, j) : 1 \leq i \leq 12, 1 \leq j \leq 12}$ . There is an edge between $(a, b)$ and…
Graph Theory
GATE CS 2014 Set 1MCQ2 marksMedium (estimate)
GATE CS 2014 Set 1, Q.62 (CS Q.52)
An ordered $n$ -tuple $(d_{1}, d_{2}, \dots, d_{n})$ with $d_{1} \geq d_{2} \geq \dots \geq d_{n}$ is called graphic if there exists a simple undirected graph with vertices having degrees…
Graph Theory
GATE CS 2014 Set 2NAT1 markEasy (estimate)
GATE CS 2014 Set 2, Q.13 (CS Q.3)
The maximum number of edges in a bipartite graph on 12 vertices is _____.
Graph Theory
GATE CS 2014 Set 2NAT2 marksEasy (estimate)
GATE CS 2014 Set 2, Q.61 (CS Q.51)
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.
Graph Theory
GATE CS 2014 Set 3MCQ2 marksEasy (estimate)
GATE CS 2014 Set 3, Q.61 (CS Q.51)
If $G$ is a forest with $n$ vertices and $k$ connected components, how many edges does $G$ have?
Graph Theory
GATE CS 2014 Set 3MCQ2 marksMedium (estimate)
GATE CS 2014 Set 3, Q.62 (CS Q.52)
Let $δ$ denote the minimum degree of a vertex in a graph. For all planar graphs on $n$ vertices with $δ \geq 3$ , which one of the following is TRUE?
Graph Theory
GATE CS 2013MCQ1 markEasy (estimate)
GATE CS 2013, Q.25 (CS Q.25)
Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even.
Graph Theory
GATE CS 2013MCQ2 marksMedium (estimate)
GATE CS 2013, Q.26 (CS Q.26)
The line graph $L (G)$ of a simple graph $G$ is defined as follows: - There is exactly one vertex $v (e)$ in $L (G)$ for each edge $e$ in $G$ . - For any two edges $e$ and $e^{'}$ in…
Graph Theory
GATE CS 2012MCQ1 markEasy (estimate)
GATE CS 2012, Q.17 (CS Q.17)
Let $G$ be a simple undirected planar graph on 10 vertices with 15 edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the plane is e...
Graph Theory
GATE CS 2012MCQ2 marksMedium (estimate)
GATE CS 2012, Q.26 (CS Q.26)
Which of the following graphs is isomorphic to the given graph? Given graph with 8 vertices and candidate graphs for isomorphism in options A, B, C, and D Stem graph and options...
Graph Theory
GATE CS 2012MCQ2 marksMedium (estimate)
GATE CS 2012, Q.38 (CS Q.38)
Let $G$ be a complete undirected graph on 6 vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length 4 in $G$ is equal to
Graph Theory · Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2011MCQ1 markEasy (estimate)
GATE CS 2011, Q.17 (CS Q.17)
$K_{4}$ and $Q_{3}$ are graphs with the following structures. Graphs K4 (complete graph on 4 vertices) and Q3 (3-dimensional hypercube graph with 8 vertices) Which one of the follow...
Graph Theory

Questions

Other topics of Engineering Mathematics