The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged graphtheory
Webpage for Graph Theory:
+1
vote
1
answer
1
Which of the following condition is sufficient to detect cycle in a directed graph?
asked
2 days
ago
in
Algorithms
by
Gangani_Son
(
145
points)

30
views
graphtheory
dfs
geekstogeeks
graphalgorithms
0
votes
0
answers
2
#geeksfoegeeks #gate #2017 #mocktest
Let G be a simple graph with 20 vertices and 8 components. If we delete a vertex in G, then number of components in G should lie between ____. (A) 8 and 20 (B) 8 and 19 (C) 7 and 19 (D) 7 and 20 Answer is (C) but i think also possible (B). anyone explain?
asked
Dec 4
in
Programming
by
Gangani_Son
(
145
points)

37
views
graphtheory
0
votes
1
answer
3
Self Doubt
If a graph with n vertices has more than $\left ( n1 \right )\left ( n2 \right ) / 2$ edges then it is connected. I am a bit confused about this question, since I can always prove that for a graph to connected you need more than $\geq n1$ edges.
asked
Dec 3
in
DS
by
jatin khachane 1
Active
(
3.2k
points)

54
views
algorithms
graphtheory
0
votes
1
answer
4
Planar Graph
Let G be a simple connected planar graph with 14 vertices and 20 edges. Number of closed regions in planar embedding of the graph is ?
asked
Dec 2
in
Graph Theory
by
Na462
Loyal
(
7.4k
points)

50
views
graphtheory
graphplanarity
0
votes
1
answer
5
Undirected Graph  Hamiltonian Cycle  NP Complete?
asked
Nov 30
in
Algorithms
by
gmrishikumar
(
461
points)

28
views
graphtheory
cycle
theoryofcomputation
pnpnpcnph
grapg
npcomplete
0
votes
0
answers
6
MIT fall 2011 algorithms
Given a directed graph G, consider forming a graph G0 as follows. Each vertex u0 ∈ G0 represents a strongly connected component (SCC) of G. There is an edge (u0 , v0 ) in G0 if there is an edge in G from the SCC corresponding to u0 to the SCC corresponding ... (u0 , v0 ) in G0 if there is an edge in G from the SCC corresponding to u0 to the SCC corresponding to v0 "
asked
Nov 19
in
Graph Theory
by
Sandy Sharma
Active
(
1.1k
points)

46
views
algorithms
graphtheory
0
votes
1
answer
7
Graph
If a graph requires k different colors for its proper coloring, then chromatic number of the graph is (a) 1 (b) k (c) k1 (d) k/2
asked
Nov 17
in
Others
by
Sriya sarkar
(
7
points)

23
views
graphtheory
0
votes
0
answers
8
Graph Theory(Eular walk)
$A)$ If a graph has closed Eularian walk, then it has an even number of edges $B)$ If $G$ be a simple graph on $9$ vertices and the sum of all degrees in $G$ is atleast $27$, then $G$ has a vertex of degree atleast $4$. Which Statement should be true? Is it possible B) to be true? And for A) I think "only if" is needed in place of "if" to be true
asked
Nov 16
in
Graph Theory
by
srestha
Veteran
(
103k
points)

69
views
graphtheory
discretemathematics
0
votes
0
answers
9
Connected Components
asked
Nov 14
in
Graph Theory
by
Na462
Loyal
(
7.4k
points)

92
views
algorithms
graphtheory
graphalgorithms
0
votes
0
answers
10
Regular graph coloring
If G is a connected kregular graph with chromatic number k+1, then find the number of edges in G?
asked
Nov 6
in
Graph Theory
by
dan31
(
287
points)

106
views
graphtheory
graphcoloring
regulargraph
0
votes
1
answer
11
Graph Connectivity
Consider the given statements S1: In a simple graph G with 6 vertices, if degree of each vertex is 2, then Euler circuit exists in G. S2:In a simple graph G, if degree of each vertex is 3 then the graph G is connected. Which of the following is/are true?
asked
Nov 6
in
Graph Theory
by
dan31
(
287
points)

77
views
graphtheory
eulergraph
graphconnectivity
0
votes
0
answers
12
Regular Graph
If a 2regular graph G has a perfect matching then which of the following is/are true? S1: G is a cycle of even length S2: Chromatic number of G is 2 S3: G is connected S4: Every component of G is an even cycle Options A) S1,S2 B)S2,S4 C)S3,S4 D)S1,S4
asked
Nov 6
in
Graph Theory
by
dan31
(
287
points)

55
views
graphtheory
discretemathematics
graph
0
votes
0
answers
13
Graph connectivity
Let G be a connected graph with 7 connected components and each component is a tree. If G has 26 edge then number of vertices in G is?
asked
Nov 6
in
Graph Theory
by
dan31
(
287
points)

148
views
graphtheory
graphconnectivity
0
votes
1
answer
14
algo graph questions
AB min value 10 is answer wrong here??
asked
Nov 6
in
Algorithms
by
I_am_winner
Junior
(
657
points)

106
views
graphtheory
0
votes
1
answer
15
Test Series
asked
Oct 29
in
Graph Theory
by
Gupta731
Active
(
2.9k
points)

92
views
discretemathematics
graphtheory
0
votes
0
answers
16
Gateforum Test Series
asked
Oct 29
in
Graph Theory
by
Gupta731
Active
(
2.9k
points)

49
views
discretemathematics
graphtheory
gateforumtestseries
0
votes
0
answers
17
Planar Graph
Can minimum degree of a planar graph be $5$? Give some example
asked
Oct 23
in
Graph Theory
by
srestha
Veteran
(
103k
points)

79
views
graphtheory
graphplanarity
0
votes
1
answer
18
Strongly connected component
How to find Strongly connected components and weakly connected components in the given graph?
asked
Oct 21
in
Graph Theory
by
Lakshman Patel RJIT
Boss
(
20k
points)

80
views
discretemathematics
graphtheory
0
votes
0
answers
19
Eulerian circuit
How many Eulerian graphs are possible?
asked
Oct 21
in
Graph Theory
by
Lakshman Patel RJIT
Boss
(
20k
points)

75
views
engineeringmathematics
discretemathematics
graphtheory
0
votes
1
answer
20
Graph theory
How many numbers of Articulation Points (or Cut Vertices) in a Graph are possible?
asked
Oct 21
in
Graph Theory
by
Lakshman Patel RJIT
Boss
(
20k
points)

41
views
discretemathematics
graphtheory
0
votes
0
answers
21
GATEBOOK2019DS21
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? $7, 5, 5, 3, 3, 2, 2, 2$ $6, 6, 6, 6, 3, 3, 2, 2, 1, 1$ $8, 7, 6, 4, 4, 3, 2, 2, 2$ $8, 7, 6, 6, 4, 4, 2, 2, 2$ II and III III and IV IV only I and IV
asked
Oct 16
in
Programming
by
GATEBOOK
Loyal
(
6k
points)

66
views
gb2019ds2
graphtheory
degreeofgraph
0
votes
2
answers
22
GATEBOOK2019DS23
A quinpartite graph is a graph whose vertices can be partitioned into five groups such that no two vertices in same group are connected via some edge. The maximum number of edges in a quinpartite graph with $10$ vertices, where cardinalities of those five sets are given as $\{2,3,2,1,2\},$ is: $16$ $20$ $26$ $39$
asked
Oct 16
in
Programming
by
GATEBOOK
Loyal
(
6k
points)

109
views
gb2019ds2
graphtheory
graphconnectivity
0
votes
0
answers
23
virtual gate graph theory
i am getting 6 as answer
asked
Oct 15
in
Graph Theory
by
Prince Sindhiya
Active
(
5.2k
points)

74
views
discretemathematics
graphtheory
0
votes
1
answer
24
Complete Matching
Consider the Bipartite graph shown. If four edges are chosen at random, what is the probability that they form a complete matching from V1 to V2 ? A. 0.039 B. 0.052 C. 0.071 D. 0.083
asked
Oct 13
in
Mathematical Logic
by
Na462
Loyal
(
7.4k
points)

65
views
graphmatching
graphtheory
discretemathematics
+2
votes
2
answers
25
Degree of vertices
Consider an undirected graph with $n$ vertices, vertex $1$ has degree $1$,while each vertex $2,3,.............,n1$ has degree $4$.The degree of vertex $n$ is unknown. Which of the following statement must be true? $A)$ Vertex $n$ has degree $1$ ... $C)$ There is a path from vertex $1$ to vertex $n$ $D)$ Spanning tree will include edge connecting vertex $1$ and vertex $n$
asked
Oct 10
in
Graph Theory
by
Lakshman Patel RJIT
Boss
(
20k
points)

69
views
discretemathematics
graphtheory
0
votes
1
answer
26
Bipartite graph
The number of ways to properly color (using just sufficient colors) a connected graph without any cycle using five colors, such a way that no two adjacent nodes have the same color?
asked
Oct 10
in
Graph Theory
by
Lakshman Patel RJIT
Boss
(
20k
points)

74
views
discretemathematics
graphtheory
0
votes
1
answer
27
Complete Graph
Consider the following graph: Number of the Hamiltonian cycles starting and ending point at $ A$ is _______
asked
Oct 10
in
Graph Theory
by
Lakshman Patel RJIT
Boss
(
20k
points)

89
views
engineeringmathematics
discretemathematics
graphtheory
0
votes
0
answers
28
Mathematics
asked
Oct 4
in
Set Theory & Algebra
by
jatinkumar
(
241
points)

28
views
graphtheory
discretemathematics
0
votes
0
answers
29
Made easy,graphs
let G be an undirected graph. consider a depthfirst traversal of G, and let T be the resulting depthfirst search tree. let you be a vertex in G and let V be the first new (unvisited) vortex visited after visiting you in the traversal. which of the following statement is always true?
asked
Oct 1
in
DS
by
KrishY
(
7
points)

45
views
graphtheory
+1
vote
0
answers
30
UGCNET CS 2017
An undirected graph G (V, E) contains n (n > 2) nodes named v1 , v2 ,...,vn. Two nodes vi and vj are connected if and only if 0 < │ i − j│ ≤2. Each edge (vi , vj ) is assigned a weight i+j. The cost of the minimum spanning tree of such a graph with 10 nodes is: A) 88 B)91 C)49 D)21
asked
Sep 28
in
Graph Theory
by
aditi19
Active
(
2.1k
points)

58
views
ugcnetnov2017iii
graphtheory
graphconnectivity
Page:
1
2
3
4
5
6
...
19
next »
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
IIT HYDERABAD M.Tech (RA) 3Years Winter Session Interview experience
INDIAN AIR FORCE
GATE BOOK _ TEST SERIES DOUBT_
Visualizing complex C code
GATE Book Test Series
Follow @csegate
Gatecse
Recent questions tagged graphtheory
Recent Blog Comments
There is one more problem. Ppl who have...
CL013924707IN rt?
I ordered the GO BOOK 6 dec ....but still i didnt...
thankyou sir
44,253
questions
49,750
answers
164,102
comments
65,847
users