menu
Login
Register
search
Log In
account_circle
Log In
Email or Username
Password
Remember
Log In
Register
I forgot my password
Register
Username
Email
Password
Register
add
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
-tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Feedback to GATE Overflow Test Takers
GATE 2021 – Online registration portal
IIT Madras MS CS Interview Experience - 2020
JEST TCS (Theoretical Computer Science) EXAM || Gateway of IISc other than GATE exam
Divisibility language and Minimum Number of States in a DFA accepting a binary number divisible by 'n'
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.4k)
Discrete Mathematics
(5.9k)
Mathematical Logic
(2.1k)
Set Theory & Algebra
(1.5k)
Combinatory
(1.4k)
Graph Theory
(884)
Probability
(1.1k)
Linear Algebra
(740)
Calculus
(609)
Digital Logic
(3k)
Programming and DS
(5.1k)
Algorithms
(4.5k)
Theory of Computation
(6.3k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.3k)
CO and Architecture
(3.5k)
Computer Networks
(4.3k)
Non GATE
(1.1k)
Others
(1.4k)
Admissions
(595)
Exam Queries
(830)
Tier 1 Placement Questions
(16)
Job Queries
(71)
Projects
(19)
Unknown Category
(873)
Recent questions and answers in Graph Theory
Recent Blog Comments
answer will be LCM(m,n) We only have to change...
How many marks did you score in the exam? this...
@arjun sir please answer this.
On exam result page, no result is being...
In your exam results page, are two results...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
Recent questions and answers in Graph Theory
37
votes
5
answers
1
GATE2001-2.15
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices? $\frac{n(n-1)} {2}$ $2^n$ $n!$ $2^\frac{n(n-1)} {2} $
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices? $\frac{n(n-1)} {2}$ $2^n$ $n!$ $2^\frac{n(n-1)} {2} $
answered
15 hours
ago
in
Graph Theory
varunrajarathnam
6.2k
views
gate2001
graph-theory
normal
counting
1
vote
4
answers
2
NIELIT 2017 DEC Scientist B - Section B: 52
Let $G$ be a simple undirected graph on $n=3x$ vertices $(x \geq 1)$ with chromatic number $3$, then maximum number of edges in $G$ is $n(n-1)/2$ $n^{n-2}$ $nx$ $n$
Let $G$ be a simple undirected graph on $n=3x$ vertices $(x \geq 1)$ with chromatic number $3$, then maximum number of edges in $G$ is $n(n-1)/2$ $n^{n-2}$ $nx$ $n$
answered
1 day
ago
in
Graph Theory
debasish paramanik
467
views
nielit2017dec-scientistb
discrete-mathematics
graph-theory
graph-coloring
4
votes
2
answers
3
Graph Theory conceptual
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree ... a vertex of degree 7. Which of the following can be the degree of the last vertex? (A) 3 (B) 0 (C) 5 (D) 4
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of ... 6 and a vertex of degree 7. Which of the following can be the degree of the last vertex? (A) 3 (B) 0 (C) 5 (D) 4
answered
Oct 14
in
Graph Theory
ayush.5
201
views
graph-theory
discrete-mathematics
0
votes
2
answers
4
Gateforum Test Series: Graph Theory - Graph Matching
answered
Oct 14
in
Graph Theory
wander
183
views
gateforum-test-series
discrete-mathematics
graph-theory
graph-matching
0
votes
2
answers
5
ME test series question on graph theory
answered
Oct 13
in
Graph Theory
arun yadav
144
views
graph-theory
0
votes
2
answers
6
Zeal Test Series 2019: Graph Theory - Graph Connectivity
answered
Oct 13
in
Graph Theory
arun yadav
232
views
zeal
graph-theory
graph-connectivity
zeal2019
1
vote
2
answers
7
Made easy Test Series:Graph Theory+Automata
Consider a graph $G$ with $2^{n}$ vertices where the level of each vertex is a $n$ bit binary string represented as $a_{0},a_{1},a_{2},.............,a_{n-1}$, where each $a_{i}$ is $0$ or $1$ ... and $y$ denote the degree of a vertex $G$ and number of connected component of $G$ for $n=8.$ The value of $x+10y$ is_____________
Consider a graph $G$ with $2^{n}$ vertices where the level of each vertex is a $n$ bit binary string represented as $a_{0},a_{1},a_{2},.............,a_{n-1}$, where each $a_{i}$ is $0$ or $1$ ... $x$ and $y$ denote the degree of a vertex $G$ and number of connected component of $G$ for $n=8.$ The value of $x+10y$ is_____________
answered
Oct 13
in
Graph Theory
arun yadav
287
views
made-easy-test-series
graph-theory
theory-of-computation
21
votes
3
answers
8
GATE1990-3-vi
Which of the following graphs is/are planner?
Which of the following graphs is/are planner?
answered
Oct 2
in
Graph Theory
codeitram
2k
views
gate1989
normal
graph-theory
graph-planarity
descriptive
6
votes
3
answers
9
GATE1988-2xvi
Write the adjacency matrix representation of the graph given in below figure.
Write the adjacency matrix representation of the graph given in below figure.
answered
Oct 2
in
Graph Theory
codeitram
1.2k
views
gate1988
descriptive
graph-theory
graph-connectivity
0
votes
1
answer
10
Gateforum Test Series: Graph Theory - Graph connectivity
answered
Sep 28
in
Graph Theory
Vineet Pandey
173
views
discrete-mathematics
graph-theory
gateforum-test-series
graph-connectivity
23
votes
6
answers
11
TIFR2018-A-9
How many ways are there to assign colours from range $\left\{1,2,\ldots,r\right\}$ to vertices of the following graph so that adjacent vertices receive distinct colours? $r^{4}$ $r^{4} - 4r^{3}$ $r^{4}-5r^{3}+8r^{2}-4r$ $r^{4}-4r^{3}+9r^{2}-3r$ $r^{4}-5r^{3}+10r^{2}-15r$
How many ways are there to assign colours from range $\left\{1,2,\ldots,r\right\}$ to vertices of the following graph so that adjacent vertices receive distinct colours? $r^{4}$ $r^{4} - 4r^{3}$ $r^{4}-5r^{3}+8r^{2}-4r$ $r^{4}-4r^{3}+9r^{2}-3r$ $r^{4}-5r^{3}+10r^{2}-15r$
answered
Sep 26
in
Graph Theory
manish_pal_sunny
1.8k
views
tifr2018
graph-theory
graph-coloring
25
votes
4
answers
12
GATE2008-IT-3
What is the chromatic number of the following graph? $2$ $3$ $4$ $5$
What is the chromatic number of the following graph? $2$ $3$ $4$ $5$
answered
Sep 26
in
Graph Theory
manish_pal_sunny
3.1k
views
gate2008-it
graph-theory
graph-coloring
normal
3
votes
3
answers
13
NIELIT 2017 DEC Scientific Assistant A - Section B: 20
Total number of simple graphs that can be drawn using six vertices are: $2^{15}$ $2^{14}$ $2^{13}$ $2^{12}$
Total number of simple graphs that can be drawn using six vertices are: $2^{15}$ $2^{14}$ $2^{13}$ $2^{12}$
answered
Sep 20
in
Graph Theory
Himanshu Kumar Gupta
168
views
nielit2017dec-assistanta
discrete-mathematics
graph-theory
7
votes
5
answers
14
ISRO2011-35
How many edges are there in a forest with $v$ vertices and $k$ components? $(v+1) - k$ $(v+1)/2 - k$ $v - k$ $v + k$
How many edges are there in a forest with $v$ vertices and $k$ components? $(v+1) - k$ $(v+1)/2 - k$ $v - k$ $v + k$
answered
Sep 18
in
Graph Theory
Dhruvil
2.7k
views
isro2011
graph-theory
0
votes
2
answers
15
NIELIT 2017 July Scientist B (IT) - Section B: 2
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph? In adjacency list representation, space is saved for sparse graphs. Deleting a vertex in adjacency list ... Adding a vertex in adjacency list representation is easier than adjacency matrix representation. All of the option.
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph? In adjacency list representation, space is saved for sparse graphs. Deleting a vertex in adjacency list representation is easier than ... matrix representation. Adding a vertex in adjacency list representation is easier than adjacency matrix representation. All of the option.
answered
Sep 18
in
Graph Theory
Dhruvil
163
views
nielit2017july-scientistb-it
discrete-mathematics
graph-theory
8
votes
3
answers
16
GATE1987-9c
Show that the number of odd-degree vertices in a finite graph is even.
Show that the number of odd-degree vertices in a finite graph is even.
answered
Sep 15
in
Graph Theory
KUSHAGRA गुप्ता
575
views
gate1987
graph-theory
degree-of-graph
descriptive
29
votes
4
answers
17
GATE2002-1.4
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is $2$ $3$ $4$ $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is $2$ $3$ $4$ $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$
answered
Sep 14
in
Graph Theory
Nishisahu
4.9k
views
gate2002
graph-theory
graph-coloring
normal
0
votes
1
answer
18
NIELIT 2016 MAR Scientist C - Section B: 20
Degree of each vertex in $K_n$ is $n$ $n-1$ $n-2$ $2n-1$
Degree of each vertex in $K_n$ is $n$ $n-1$ $n-2$ $2n-1$
asked
Apr 2
in
Graph Theory
Lakshman Patel RJIT
44
views
nielit2016mar-scientistc
discrete-mathematics
graph-theory
0
votes
1
answer
19
NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 7
The number of the edges in a regular graph of degree $’d’$ and $’n’$ vertices is Maximum of $n,d$ $n+d$ $nd$ $nd/2$
The number of the edges in a regular graph of degree $’d’$ and $’n’$ vertices is Maximum of $n,d$ $n+d$ $nd$ $nd/2$
asked
Apr 1
in
Graph Theory
Lakshman Patel RJIT
92
views
nielit2017oct-assistanta-cs
discrete-mathematics
graph-theory
degree-of-graph
1
vote
1
answer
20
NIELIT 2017 DEC Scientific Assistant A - Section B: 38
If a planner graph, having $25$ vertices divides the plane into $17$ different regions. Then how many edges are used to connect the vertices in this graph. $20$ $30$ $40$ $50$
If a planner graph, having $25$ vertices divides the plane into $17$ different regions. Then how many edges are used to connect the vertices in this graph. $20$ $30$ $40$ $50$
asked
Mar 31
in
Graph Theory
Lakshman Patel RJIT
89
views
nielit2017dec-assistanta
discrete-mathematics
graph-theory
graph-planarity
0
votes
2
answers
21
NIELIT 2016 MAR Scientist B - Section B: 1
The number of ways to cut a six sided convex polygon whose vertices are labeled into four triangles using diagonal lines that do not cross is $13$ $14$ $12$ $11$
The number of ways to cut a six sided convex polygon whose vertices are labeled into four triangles using diagonal lines that do not cross is $13$ $14$ $12$ $11$
asked
Mar 31
in
Graph Theory
Lakshman Patel RJIT
140
views
nielit2016mar-scientistb
discrete-mathematics
graph-theory
0
votes
1
answer
22
NIELIT 2016 MAR Scientist B - Section B: 3
Maximum degree of any node in a simple graph with $n$ vertices is $n-1$ $n$ $n/2$ $n-2$
Maximum degree of any node in a simple graph with $n$ vertices is $n-1$ $n$ $n/2$ $n-2$
asked
Mar 31
in
Graph Theory
Lakshman Patel RJIT
100
views
nielit2016mar-scientistb
discrete-mathematics
graph-theory
degree-of-graph
1
vote
1
answer
23
NIELIT 2016 DEC Scientist B (CS) - Section B: 5
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 equal to: $3$ $4$ $5$ $6$
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 equal to: $3$ $4$ $5$ $6$
asked
Mar 31
in
Graph Theory
Lakshman Patel RJIT
106
views
nielit2016dec-scientistb-cs
discrete-mathematics
graph-theory
graph-planarity
0
votes
1
answer
24
NIELIT 2017 July Scientist B (IT) - Section B: 1
Given an undirected graph $G$ with $V$ vertices and $E$ edges, the sum of the degrees of all vertices is $E$ $2E$ $V$ $2V$
Given an undirected graph $G$ with $V$ vertices and $E$ edges, the sum of the degrees of all vertices is $E$ $2E$ $V$ $2V$
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
705
views
nielit2017july-scientistb-it
discrete-mathematics
graph-theory
degree-of-graph
0
votes
1
answer
25
NIELIT 2017 July Scientist B (IT) - Section B: 3
A path in graph $G$, which contains every vertex of $G$ and only once? Euler circuit Hamiltonian path Euler Path Hamiltonian Circuit
A path in graph $G$, which contains every vertex of $G$ and only once? Euler circuit Hamiltonian path Euler Path Hamiltonian Circuit
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
127
views
nielit2017july-scientistb-it
discrete-mathematics
graph-theory
0
votes
1
answer
26
NIELIT 2017 July Scientist B (IT) - Section B: 5
In a given following graph among the following sequences: abeghf abfehg abfhge afghbe Which are depth first traversals of the above graph? I,II and IV only I and IV only II,III and IV only I,III and IV only
In a given following graph among the following sequences: abeghf abfehg abfhge afghbe Which are depth first traversals of the above graph? I,II and IV only I and IV only II,III and IV only I,III and IV only
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
114
views
nielit2017july-scientistb-it
discrete-mathematics
graph-theory
dfs
0
votes
1
answer
27
NIELIT 2017 July Scientist B (IT) - Section B: 6
Considering the following graph, which one of the following set of edged represents all the bridges of the given graph? $(a,b), (e,f)$ $(a,b), (a,c)$ $(c,d), (d,h)$ $(a,b)$
Considering the following graph, which one of the following set of edged represents all the bridges of the given graph? $(a,b), (e,f)$ $(a,b), (a,c)$ $(c,d), (d,h)$ $(a,b)$
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
82
views
nielit2017july-scientistb-it
discrete-mathematics
graph-theory
bridges
0
votes
1
answer
28
NIELIT 2017 July Scientist B (IT) - Section B: 7
Which of the following statements is/are TRUE? $S1$:The existence of an Euler circuit implies that an Euler path exists. $S2$:The existence of an Euler path implies that an Euler circuit exists. $S1$ is true. $S2$ is true. $S1$ and $S2$ both are true. $S1$ and $S2$ both are false.
Which of the following statements is/are TRUE? $S1$:The existence of an Euler circuit implies that an Euler path exists. $S2$:The existence of an Euler path implies that an Euler circuit exists. $S1$ is true. $S2$ is true. $S1$ and $S2$ both are true. $S1$ and $S2$ both are false.
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
103
views
nielit2017july-scientistb-it
discrete-mathematics
graph-theory
euler-graph
0
votes
1
answer
29
NIELIT 2017 July Scientist B (IT) - Section B: 8
A connected planar graph divides the plane into a number of regions. If the graph has eight vertices and these are linked by $13$ edges, then the number of regions is: $5$ $6$ $7$ $8$
A connected planar graph divides the plane into a number of regions. If the graph has eight vertices and these are linked by $13$ edges, then the number of regions is: $5$ $6$ $7$ $8$
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
75
views
nielit2017july-scientistb-it
discrete-mathematics
graph-theory
graph-planarity
0
votes
1
answer
30
NIELIT 2017 July Scientist B (IT) - Section B: 12
Let $G$ be a simple connected planar graph with $13$ vertices and $19$ edges. Then, the number of faces in the planar embedding of the graph is $6$ $8$ $9$ $13$
Let $G$ be a simple connected planar graph with $13$ vertices and $19$ edges. Then, the number of faces in the planar embedding of the graph is $6$ $8$ $9$ $13$
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
62
views
nielit2017july-scientistb-it
discrete-mathematics
graph-theory
graph-planarity
0
votes
1
answer
31
NIELIT 2017 July Scientist B (IT) - Section B: 15
The number of diagonals that can be drawn by joining the vertices of an octagon is $28$ $48$ $20$ None of the option
The number of diagonals that can be drawn by joining the vertices of an octagon is $28$ $48$ $20$ None of the option
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
62
views
nielit2017july-scientistb-it
discrete-mathematics
graph-theory
0
votes
1
answer
32
NIELIT 2017 July Scientist B (CS) - Section B: 2
Which of the following statements is/are TRUE for an undirected graph? Number of odd degree vertices is even Sum of degrees of all vertices is even P only Q only Both P and Q Neither P nor Q
Which of the following statements is/are TRUE for an undirected graph? Number of odd degree vertices is even Sum of degrees of all vertices is even P only Q only Both P and Q Neither P nor Q
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
131
views
nielit2017july-scientistb-cs
discrete-mathematics
graph-theory
degree-of-graph
0
votes
3
answers
33
NIELIT 2017 July Scientist B (CS) - Section B: 11
Consider the following graph $L$ and find the bridges,if any. No bridge $\{d,e\}$ $\{c,d\}$ $\{c,d\}$ and $\{c,f\}$
Consider the following graph $L$ and find the bridges,if any. No bridge $\{d,e\}$ $\{c,d\}$ $\{c,d\}$ and $\{c,f\}$
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
146
views
nielit2017july-scientistb-cs
discrete-mathematics
graph-theory
bridges
0
votes
3
answers
34
NIELIT 2017 July Scientist B (CS) - Section B: 12
The following graph has no Euler circuit because It has $7$ vertices. It is even-valent (all vertices have even valence). It is not connected. It does not have a Euler circuit.
The following graph has no Euler circuit because It has $7$ vertices. It is even-valent (all vertices have even valence). It is not connected. It does not have a Euler circuit.
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
315
views
nielit2017july-scientistb-cs
discrete-mathematics
graph-theory
euler-graph
0
votes
7
answers
35
NIELIT 2017 July Scientist B (CS) - Section B: 13
For the graph shown, which of the following paths is a Hamilton circuit? $ABCDCFDEFAEA$ $AEDCBAF$ $AEFDCBA$ $AFCDEBA$
For the graph shown, which of the following paths is a Hamilton circuit? $ABCDCFDEFAEA$ $AEDCBAF$ $AEFDCBA$ $AFCDEBA$
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
304
views
nielit2017july-scientistb-cs
discrete-mathematics
graph-theory
0
votes
4
answers
36
NIELIT 2017 July Scientist B (CS) - Section B: 14
If $G$ is an undirected planar graph on $n$ vertices with $e$ edges then $e\leq n$ $e\leq 2n$ $e\leq 3n$ None of the option
If $G$ is an undirected planar graph on $n$ vertices with $e$ edges then $e\leq n$ $e\leq 2n$ $e\leq 3n$ None of the option
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
506
views
nielit2017july-scientistb-cs
discrete-mathematics
graph-theory
graph-planarity
0
votes
2
answers
37
NIELIT 2017 July Scientist B (CS) - Section B: 15
Choose the most appropriate definition of plane graph. A simple graph which is isomorphic to hamiltonian graph. A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non-empty disjoint subset $X$ and ... in a plane in such a way that any pair of edges meet only at their end vertices. None of the option.
Choose the most appropriate definition of plane graph. A simple graph which is isomorphic to hamiltonian graph. A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non-empty disjoint subset $X$ and $Y$ in such a way that each edge ... . A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices. None of the option.
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
238
views
nielit2017july-scientistb-cs
discrete-mathematics
graph-theory
graph-planarity
0
votes
1
answer
38
NIELIT 2017 DEC Scientist B - Section B: 23
Let $G$ be a complete undirected graph on $8$ vertices. If vertices of $G$ are labelled, then the number of distinct cycles of length $5$ in $G$ is equal to: $15$ $30$ $56$ $60$
Let $G$ be a complete undirected graph on $8$ vertices. If vertices of $G$ are labelled, then the number of distinct cycles of length $5$ in $G$ is equal to: $15$ $30$ $56$ $60$
asked
Mar 30
in
Graph Theory
Lakshman Patel RJIT
247
views
nielit2017dec-scientistb
discrete-mathematics
graph-theory
cycle
0
votes
1
answer
39
UGCNET-Dec2007-II: 2
The number of edges in a complete graph with $‘n’$ vertices is equal to : $n(n-1)$ $\large\frac{n(n-1)}{2}$ $n^2$ $2n-1$
The number of edges in a complete graph with $‘n’$ vertices is equal to : $n(n-1)$ $\large\frac{n(n-1)}{2}$ $n^2$ $2n-1$
asked
Mar 28
in
Graph Theory
jothee
81
views
ugcnetdec2007ii
0
votes
2
answers
40
UGCNET-Dec2006-II: 3
The number of edges in a complete graph with $N$ vertices is equal to : $N (N−1)$ $2N−1$ $N−1$ $N(N−1)/2$
The number of edges in a complete graph with $N$ vertices is equal to : $N (N−1)$ $2N−1$ $N−1$ $N(N−1)/2$
asked
Mar 27
in
Graph Theory
jothee
151
views
ugcnetdec2006ii
To see more, click for all the
questions in this category
.
...