ExamSIDE
Questions
ExamSIDE.Com
Discrete Mathematics
Mathematical Logic
Probability
Set Theory & Algebra
Combinatorics
Linear Algebra
Graph Theory
Calculus
Joint Entrance Examination
JEE Main
Chemistry
Physics
Mathematics
JEE Advanced
Physics
Chemistry
Mathematics
WB JEE
Physics
Chemistry
Mathematics
Graduate Aptitude Test in Engineering
GATE CSE
Discrete Mathematics
Programming Languages
Theory of Computation
Operating Systems
Digital Logic
Computer Organization
Database Management System
Data Structures
Computer Networks
Algorithms
Compiler Design
Software Engineering
Web Technologies
General Aptitude
GATE ECE
Network Theory
Control Systems
Electronic Devices and VLSI
Analog Circuits
Digital Circuits
Microprocessors
Signals and Systems
Communications
Electromagnetics
General Aptitude
Engineering Mathematics
GATE EE
Electromagnetic Fields
Signals and Systems
Engineering Mathematics
General Aptitude
Power Electronics
Power System Analysis
Analog Electronics
Control Systems
Digital Electronics
Electrical Machines
Electric Circuits
Electrical and Electronics Measurement
GATE ME
Engineering Mechanics
Strength of Materials
Theory of Machines
Engineering Mathematics
Machine Design
Fluid Mechanics
Turbo Machinery
Heat Transfer
Thermodynamics
Production Engineering
Industrial Engineering
General Aptitude
GATE CE
Construction Material and Management
Geomatics Engineering Or Surveying
Engineering Mechanics
Hydrology
Transportation Engineering
Strength of Materials Or Solid Mechanics
Reinforced Cement Concrete
Steel Structures
Irrigation
Environmental Engineering
Engineering Mathematics
Structural Analysis
Geotechnical Engineering
Fluid Mechanics and Hydraulic Machines
General Aptitude
GATE PI
Fluid Mechanics
Metrology
Theory of Machines
Engineering Mathematics
Heat Transfer
Machine Tools and Machining
Industrial Engineering
Engineering Mechanics
Strength of Materials
Thermodynamics
Machine Design
Casting
Joining of Materials
Metal Forming
GATE IN
Engineering Mathematics
Medical
NEET
Biology
Chemistry
Physics
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
START HERE
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
GO TO QUESTION
The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are T...
GATE CSE 2022
GO TO QUESTION
Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements...
GATE CSE 2022
GO TO QUESTION
Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, t...
GATE CSE 2022
GO TO QUESTION
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can...
GATE CSE 2022
GO TO QUESTION
Which of the following statements is/are TRUE for a group G?
GATE CSE 2022
GO TO QUESTION
Let G be a connected undirected weighted graph. Consider the following two statements. S1: There exists a minimum weigh...
GATE CSE 2021 Set 2
GO TO QUESTION
Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in...
GATE CSE 2019
GO TO QUESTION
The chromatic number of the following graph is _______. ...
GATE CSE 2018
GO TO QUESTION
Let $$G$$ be a finite group on $$84$$ elements. The size of a largest possible proper subgroup of $$G$$ is ________.
GATE CSE 2018
GO TO QUESTION
The minimum number of colours that is sufficient to vertex-colour any planar graph is _____________ .
GATE CSE 2016 Set 2
GO TO QUESTION
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
GO TO QUESTION
The maximum number of edges in a bipartite graph on $$12$$ vertices is _________.
GATE CSE 2014 Set 1
GO TO QUESTION
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
GO TO QUESTION
Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: ...
GATE CSE 2013
GO TO QUESTION
Consider an undirected random$$^ \circ $$ graph of eight vertices. The probability that there is an edge between a pair ...
GATE CSE 2013
GO TO QUESTION
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
GO TO QUESTION
$$K4$$ and $$Q3$$ are graphs with the following structures. Which one of the following statements is TRUE in relation t...
GATE CSE 2011
GO TO QUESTION
Let $$G$$ $$\,\,\,\,\, = \,\,\,\left( {V,\,\,\,\,\,E} \right)$$ be a graph. Define $$\xi \left( G \right) = \sum\limits_...
GATE CSE 2010
GO TO QUESTION
What is the chromatic number of an $$n$$-vertex simple connected graph which does not contain any odd length cycle? Assu...
GATE CSE 2009
GO TO QUESTION
Which one of the following is TRUE for any simple connected undirected graph with more than $$2$$ vertices?
GATE CSE 2009
GO TO QUESTION
What is the chromatic number of the following graph? ...
GATE CSE 2008
GO TO QUESTION
What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes?
GATE CSE 2008
GO TO QUESTION
Let $$G$$ be the non-planar graph with minimum possible number of edges. Then $$G$$ has
GATE CSE 2007
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
The maximum number of binary trees that can be formed with three unlabeled nodes is:
GATE CSE 2007
GO TO QUESTION
Consider a weighted complete graph $$G$$ on the vertex set $$\left\{ {{v_1},\,\,\,{v_2},....,\,\,\,{v_n}} \right\}$$ suc...
GATE CSE 2006
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
What is the maximum number of edges in an acyclic undirected graph with $$n$$ vertices?
GATE CSE 2004
GO TO QUESTION
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
GO TO QUESTION
Maximum number of edges in a n - node undirected graph without self loops is
GATE CSE 2002
GO TO QUESTION
The number of distinct simple graph with upto three nodes is
GATE CSE 1994
GO TO QUESTION
Which of the following is/are tautology?
GATE CSE 1992
GO TO QUESTION
A non-planar graph with minimum number of vertices has
GATE CSE 1992
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
If $$G$$ is a forest with $$n$$ vertices and $$k$$ connected components, how many edges does $$G$$ have?
GATE CSE 2014 Set 3
GO TO QUESTION
A cycle on $$n$$ vertices is isomorphic to its complement. The value of $$n$$ is __________.
GATE CSE 2014 Set 2
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
The line graph $$L(G)$$ of a simple graph $$G$$ is defined as follows: $$\,\,\,\,$$There is exactly one vertex $$v(e)$$ ...
GATE CSE 2013
GO TO QUESTION
Let $$G$$ be a complete undirected graph on $$6$$ vertices. If vertices of $$G$$ $$\,\,\,\,$$ are labeled, then the numb...
GATE CSE 2012
GO TO QUESTION
Which of the following graphs is isomorphic to ...
GATE CSE 2012
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
$$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
GO TO QUESTION
$$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
GO TO QUESTION
Which of the following statements is true for every planar graph on $$n$$ vertices?
GATE CSE 2008
GO TO QUESTION
Which of the following graphs has an Eulerian circuit?
GATE CSE 2007
GO TO QUESTION
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
GO TO QUESTION
Consider the undirected graph $$G$$ defined as follows. The vertices of $$G$$ are bit strings of length $$n$$. We have a...
GATE CSE 2006
GO TO QUESTION
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
GO TO QUESTION
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
GO TO QUESTION
Which one of the following graphs is NOT planar? ...
GATE CSE 2005
GO TO QUESTION
What is the number of vertices in an undirected connected graph with $$27$$ edges, $$6$$ vertices of degree $$2$$, $$\,\...
GATE CSE 2004
GO TO QUESTION
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
GO TO QUESTION
How many graphs on $$n$$ labeled vertices exist which have at least $$\left( {{n^2} - 3n} \right)/2\,\,\,$$ edges?
GATE CSE 2004
GO TO QUESTION
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned th...
GATE CSE 2004
GO TO QUESTION
How many perfect matchings are there in a complete graph of 6 vertices?
GATE CSE 2003
GO TO QUESTION
$$A$$ graph $$G$$ $$=$$ $$(V, E)$$ satisfies $$\left| E \right| \le \,3\left| V \right| - 6.$$ The min-degree of $$G$$ ...
GATE CSE 2003
GO TO QUESTION
how many undirected graphs (not necessarily connected) can be constructed out of a given $$\,\,\,\,V = \left\{ {{v_1},\,...
GATE CSE 2001
GO TO QUESTION
Prove that in a finite graph, the number of vertices of odd degree is always even.
GATE CSE 1995
GO TO QUESTION
Maximum number of edges in a planar graph with $$n$$ vertices is _______ .
GATE CSE 1992
GO TO QUESTION
The maximum number of possible edges in an undirected graph with a vertices and $$k$$ components is _________ .
GATE CSE 1991
GO TO QUESTION
A graph is planar if and only if,
GATE CSE 1990
GO TO QUESTION
Which of the following graphs is / are planar? (see fig.) ...
GATE CSE 1989
GO TO QUESTION
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
GO TO QUESTION
How many minimum spanning tress does the following graph have? Draw them (Weights are assigned to the edges). ...
GATE CSE 1995
GO TO QUESTION
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