NEW
New Website Launch
Experience the best way to solve previous year questions with mock tests (very detailed analysis), bookmark your favourite questions, practice etc...
VISIT NOW

GATE CSE

Graph Theory

Discrete Mathematics

Previous Years Questions

Marks 1

More
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?...
GATE CSE 2022
The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are T...
GATE CSE 2022
Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements...
GATE CSE 2022
Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, t...
GATE CSE 2022
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can...
GATE CSE 2022
Which of the following statements is/are TRUE for a group G?
GATE CSE 2022
Let G be a connected undirected weighted graph. Consider the following two statements. S1: There exists a minimum weigh...
GATE CSE 2021 Set 2
Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in...
GATE CSE 2019
The chromatic number of the following graph is _______. ...
GATE CSE 2018
Let $$G$$ be a finite group on $$84$$ elements. The size of a largest possible proper subgroup of $$G$$ is ________.
GATE CSE 2018
The minimum number of colours that is sufficient to vertex-colour any planar graph is _____________ .
GATE CSE 2016 Set 2
let $$G$$ be a group with $$15$$ elements. Let $$L$$ be a subgroup of $$G$$. It is known that $$L \ne G$$ and that the s...
GATE CSE 2014 Set 3
The maximum number of edges in a bipartite graph on $$12$$ vertices is _________.
GATE CSE 2014 Set 1
Let $$G = \left( {V,E} \right)$$ be a directed graph where $$V$$ is the set of vertices and $$E$$ the set of edges. Then...
GATE CSE 2014 Set 1
Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: ...
GATE CSE 2013
Consider an undirected random$$^ \circ $$ graph of eight vertices. The probability that there is an edge between a pair ...
GATE CSE 2013
Let G be a simple undirected planner graph on 10 vertices with 15 edges. If G is a connected graph, then the number of b...
GATE CSE 2012
$$K4$$ and $$Q3$$ are graphs with the following structures. Which one of the following statements is TRUE in relation t...
GATE CSE 2011
Let $$G$$ $$\,\,\,\,\, = \,\,\,\left( {V,\,\,\,\,\,E} \right)$$ be a graph. Define $$\xi \left( G \right) = \sum\limits_...
GATE CSE 2010
Which one of the following is TRUE for any simple connected undirected graph with more than $$2$$ vertices?
GATE CSE 2009
What is the chromatic number of an $$n$$-vertex simple connected graph which does not contain any odd length cycle? Assu...
GATE CSE 2009
What is the chromatic number of the following graph? ...
GATE CSE 2008
What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes?
GATE CSE 2008
The maximum number of binary trees that can be formed with three unlabeled nodes is:
GATE CSE 2007
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a bi...
GATE CSE 2007
Consider a weighted undirected graph with positive edge weights and let $$uv$$ be an edge in the graph. It is known that...
GATE CSE 2007
Let $$G$$ be the non-planar graph with minimum possible number of edges. Then $$G$$ has
GATE CSE 2007
Consider a weighted complete graph $$G$$ on the vertex set $$\left\{ {{v_1},\,\,\,{v_2},....,\,\,\,{v_n}} \right\}$$ suc...
GATE CSE 2006
If all the edge weights of an undirected graph are positive, then any subject of edges that connects all the vertices an...
GATE CSE 2006
Let $$G$$ be the simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of $$G$$ is 8. Then, ...
GATE CSE 2005
Let $$G$$ be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embe...
GATE CSE 2005
What is the maximum number of edges in an acyclic undirected graph with $$n$$ vertices?
GATE CSE 2004
Let $$G$$ be an arbitrary graph with $$n$$ nodes and $$k$$ components. If a vertex is removed from $$G$$, the number of ...
GATE CSE 2003
Maximum number of edges in a n - node undirected graph without self loops is
GATE CSE 2002
The number of distinct simple graph with upto three nodes is
GATE CSE 1994
Which of the following is/are tautology?
GATE CSE 1992
A non-planar graph with minimum number of vertices has
GATE CSE 1992

Marks 2

More
In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is ______
GATE CSE 2021 Set 1
Let G be a group order 6, and H be a subgroup of G such that 1 < |H| < 6. Which one of the following options is co...
GATE CSE 2021 Set 1
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects ...
GATE CSE 2021 Set 1
Graph G is obtained by adding vertex s to K3,4 and making s adjacent to every vertex of K3,4. The minimum number of colo...
GATE CSE 2020
In a connected graph, bridge is an edge whose removal disconnects a graph. Which one of the following statements is true...
GATE CSE 2015 Set 2
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $$n$$ vertices...
GATE CSE 2015 Set 2
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edg...
GATE CSE 2015 Set 1
Suppose L = { p, q, r, s, t } is a lattice represented by the following Hasse diagram: For any $$x, y ∈ L$$, not necess...
GATE CSE 2015 Set 1
If $$G$$ is a forest with $$n$$ vertices and $$k$$ connected components, how many edges does $$G$$ have?
GATE CSE 2014 Set 3
Consider an undirectional graph $$G$$ where self-loops are not allowed. The vertex set of $$G$$ is $$\left\{ {\left( {i,...
GATE CSE 2014 Set 1
A cycle on $$n$$ vertices is isomorphic to its complement. The value of $$n$$ is __________.
GATE CSE 2014 Set 2
Let $$\delta $$ denote the minimum degree of a vertex in a graph. For all planar graphs on $$n$$ vertices with $$\delta ...
GATE CSE 2014 Set 3
An ordered $$n$$-tuple $$\left( {{d_1},\,\,{d_2},\,....,{d_n}} \right)$$ with $${{d_1} \ge ,\,\,{d_2} \ge .... \ge {d_n}...
GATE CSE 2014 Set 1
The line graph $$L(G)$$ of a simple graph $$G$$ is defined as follows: $$\,\,\,\,$$There is exactly one vertex $$v(e)$$ ...
GATE CSE 2013
Let $$G$$ be a complete undirected graph on $$6$$ vertices. If vertices of $$G$$ $$\,\,\,\,$$ are labeled, then the numb...
GATE CSE 2012
Which of the following graphs is isomorphic to ...
GATE CSE 2012
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Whic...
GATE CSE 2010
A binary tree with $$n>1$$ nodes has $${n_1}$$, $${n_2}$$ and $${n_3}$$ nodes of degree one, two and three respective...
GATE CSE 2008
A binary tree with $$n>1$$ nodes has $${n_1}$$, $${n_2}$$ and $${n_3}$$ nodes of degree one, two and three respective...
GATE CSE 2008
$$G$$ is a graph on $$n$$ vertices and $$2n-2$$ edges. The edges of $$G$$ can be partitioned into two edge-disjoint span...
GATE CSE 2008
$$G$$ is a simple undirected graph. Some vertices of $$G$$ are of odd degree. Add a node $$v$$ to $$G$$ and make it adja...
GATE CSE 2008
Which of the following statements is true for every planar graph on $$n$$ vertices?
GATE CSE 2008
Let Graph$$(x)$$ be a predicate which denotes that $$x$$ is a graph. Let Connected$$(x)$$ be a predicate which denotes t...
GATE CSE 2007
Which of the following graphs has an Eulerian circuit?
GATE CSE 2007
Consider the undirected graph $$G$$ defined as follows. The vertices of $$G$$ are bit strings of length $$n$$. We have a...
GATE CSE 2006
The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices ...
GATE CSE 2006
The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices ...
GATE CSE 2006
Which one of the following graphs is NOT planar? ...
GATE CSE 2005
What is the number of vertices in an undirected connected graph with $$27$$ edges, $$6$$ vertices of degree $$2$$, $$\,\...
GATE CSE 2004
Let $${G_1} = \left( {V,\,{E_1}} \right)$$ and $${G_2} = \left( {V,\,{E_2}} \right)$$ be connected graphs on the same ve...
GATE CSE 2004
How many graphs on $$n$$ labeled vertices exist which have at least $$\left( {{n^2} - 3n} \right)/2\,\,\,$$ edges?
GATE CSE 2004
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned th...
GATE CSE 2004
How many perfect matchings are there in a complete graph of 6 vertices?
GATE CSE 2003
$$A$$ graph $$G$$ $$=$$ $$(V, E)$$ satisfies $$\left| E \right| \le \,3\left| V \right| - 6.$$ The min-degree of $$G$$ ...
GATE CSE 2003
how many undirected graphs (not necessarily connected) can be constructed out of a given $$\,\,\,\,V = \left\{ {{v_1},\,...
GATE CSE 2001
Prove that in a finite graph, the number of vertices of odd degree is always even.
GATE CSE 1995
Maximum number of edges in a planar graph with $$n$$ vertices is _______ .
GATE CSE 1992
The maximum number of possible edges in an undirected graph with a vertices and $$k$$ components is _________ .
GATE CSE 1991
A graph is planar if and only if,
GATE CSE 1990
Which of the following graphs is / are planar? (see fig.) ...
GATE CSE 1989

Marks 5

More
Let $$G$$ be a connected, undirected graph. A $$cut$$ in $$G$$ is a set of edges whose removal results in $$G$$ being br...
GATE CSE 1999
How many minimum spanning tress does the following graph have? Draw them (Weights are assigned to the edges). ...
GATE CSE 1995

Joint Entrance Examination

JEE Main JEE Advanced WB JEE

Graduate Aptitude Test in Engineering

GATE CSE GATE ECE GATE EE GATE ME GATE CE GATE PI GATE IN

Medical

NEET

CBSE

Class 12