The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook 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:
0
votes
0
answers
1
JEST 2019
A directed graph with n vertices, in which each vertex has exactly 3 outgoing edges. Which one is true? A) All the vertices have indegree = 3 . B) Some vertices will have indegree exactly 3. C)Some vertices have indegree atleast 3. D) Some of the vertices have indegree atmost 3
asked
4 days
ago
in
Graph Theory
by
Sayan Bose
Loyal
(
5.9k
points)

32
views
jest
graphtheory
0
votes
1
answer
2
JEST Sample Question4
A tournament is a directed graph in which there is exactly one directed edge between every pair of vertices. Let Tn be a tournament on n vertices. (a) Use induction to prove the following statement: Tn has a directed hamiltonian path (a directed ... or a simple description of the steps in the algorithm, will suffice. What is the worst case time complexity of your algorithm?
asked
Feb 15
in
Algorithms
by
sripo
Active
(
1.5k
points)

38
views
jest
gate
algorithms
discretemathematics
graphtheory
0
votes
1
answer
3
JEST Sample Question5
Describe two different data structures to represent a graph. For each such representation, specify a simple property about the graph that can be more efficiently checked in that representation than in the other representation. Indicate the worst case time required for verifying both of your properties in either representation.
asked
Feb 15
in
Algorithms
by
sripo
Active
(
1.5k
points)

17
views
jest
gate
algorithms
graphtheory
graphalgorithms
0
votes
4
answers
4
GATE201912
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 $n!$ $(n1)!$ $1$ $\frac{(n1)!}{2}$
asked
Feb 7
in
Graph Theory
by
Arjun
Veteran
(
384k
points)

2.1k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+1
vote
1
answer
5
GATE201938
Let $G$ be any connected, weighted, undirected graph. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimumweight edge crossing the cut. Which of the following statements is/are TRUE? I only II only Both I and II Neither I nor II
asked
Feb 7
in
Graph Theory
by
Arjun
Veteran
(
384k
points)

1.9k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
0
votes
1
answer
6
GATE 2019 8
Q.8 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 1. (n1)!/2 2. 1 3.(n1)! 4. n!
asked
Feb 7
in
Graph Theory
by
Ram Swaroop
Active
(
2.2k
points)

211
views
usergate2019
usermod
discretemathematics
graphtheory
0
votes
0
answers
7
GeeksforGeeks
Let G be a graph with no isolated vertices, and let M be a maximum matching of G. For each vertex v not saturated by M, choose an edge incident to v. Let T be the set of all the chosen edges, and let L = M ∪ T. Which of the following option is TRUE? A L is always ... G. B L is always a minimum edge cover of G. C Both (A) and (B) D Neither (A) nor (B) Can anyone pls help solving this?
asked
Jan 30
in
Graph Theory
by
Ashish Goyal
(
337
points)

90
views
graphmatching
discretemathematics
graphtheory
testseries
0
votes
1
answer
8
#GRAPH THEORY
A simple regular graph n vertices and 24 edges, find all possible values of n.
asked
Jan 29
in
Graph Theory
by
amit166
Junior
(
693
points)

59
views
graphtheory
0
votes
0
answers
9
Counting
asked
Jan 25
in
Graph Theory
by
screddy1313
(
401
points)

29
views
discretemathematics
graphtheory
engineeringmathematics
chromaticnumbers
#counting
0
votes
0
answers
10
Number of sub graphs possible
Number of labelled subgraphs possible for the graph given below______________
asked
Jan 25
in
DS
by
Nandkishor3939
Active
(
1.2k
points)

65
views
graphtheory
datastructure
0
votes
1
answer
11
Virtual Gate
A complete graph on n vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let G be a complete graph on 10 vertices. Let u, v, w be three distinct vertices in G. How many simple paths are there from u to v going through w?
asked
Jan 24
in
Graph Theory
by
sudharshan
(
289
points)

59
views
discretemathematics
graphtheory
testseries
0
votes
0
answers
12
Homomorphic and Isomorphic graph
This a random question came into my mind… Are the below statements true: 1] If a graph is Homomorphic to our graph then it is also Isomorphic to that graph. 2]If a graph is Isomorphic to our graph then it is also Homomorphic graph.
asked
Jan 21
in
Set Theory & Algebra
by
Nandkishor3939
Active
(
1.2k
points)

31
views
graphisomorphism
graphtheory
groups
0
votes
1
answer
13
made easy test
The number of labelled subgraphs possible for the graph given below.
asked
Jan 19
in
DS
by
snaily16
(
255
points)

214
views
madeeasytestseries
discretemathematics
graphtheory
0
votes
0
answers
14
Algorithm questions on graphs
let Gn be a complete graph on n vertices where n>2 such that each vertex is labeled by a distinct number 1,2, 3, 4, …, n , and each edge is labeled by the sum of its endpoint labels. Let f(Gn) be the minimum sum of edge labels in any path that touches every vertex in exactly once. How many values of satisfy f(Gn)2013 (mod n) ?___________
asked
Jan 19
in
Algorithms
by
Iamniks4
(
63
points)

14
views
graphtheory
0
votes
0
answers
15
Number of Cut edges
If G is a connected simple graph with 10 vertices in which degree of every vertex is 2 then number of cut edges in G is ?
asked
Jan 19
in
Graph Theory
by
Na462
Loyal
(
8.6k
points)

44
views
algorithms
graphtheory
acetestseries
0
votes
1
answer
16
ME test series question on graph theory
asked
Jan 17
in
Graph Theory
by
Shankar Kakde
(
369
points)

55
views
graphtheory
0
votes
2
answers
17
Applied Course 2019 Mock136
Naveen invited seven of his friends to a party. At the party, several pairs of people shook hands, although no one shook hands with themselves or shook hands with the same person more than once. After the party, Naveen asked each of his seven friends ... distinct positive integers. Given that his friends were truthful, how many hands did Naveen shake? $4$ $5$ $6$ $7$
asked
Jan 16
in
Graph Theory
by
Applied Course
Junior
(
757
points)

82
views
appldcourse2019mock1
graphtheory
0
votes
0
answers
18
Made Easy
What are all the conditions for the degree sequence to be graphic?
asked
Jan 16
in
Algorithms
by
gate_dreams
(
309
points)

29
views
graphtheory
madeeasytestseries
+1
vote
2
answers
19
Tripartite Graph
The number of vertices,edges and colors required for proper coloring in Tripartite graph K<3,2,5> will be : 10 , 31 , 3 10 , 30 , 3 10 , 30 , 2 None
asked
Jan 16
in
Graph Theory
by
Na462
Loyal
(
8.6k
points)

59
views
graphtheory
discretemathematics
madeeasytestseries
+1
vote
1
answer
20
Vertex Connectivity
The Vertex Connectivity of Graph is : 1 2 3 None
asked
Jan 16
in
Graph Theory
by
Na462
Loyal
(
8.6k
points)

49
views
graphtheory
graphconnectivity
madeeasytestseries
+2
votes
1
answer
21
How many Binary Search Trees are possible for a labelled nodes?
Let us there are n nodes which are labelled. Then the number of trees possible is given by the Catalan Number i.e $\binom{2n}{n} / (n+1)$ Then the binary search trees possible is just 1?
asked
Jan 16
in
DS
by
sripo
Active
(
1.5k
points)

83
views
algorithms
graphtheory
binarysearchtree
binarysearch
binarytree
trees
datastructure
0
votes
1
answer
22
CUT VERTEX
plz solve this problem..
asked
Jan 9
in
Mathematical Logic
by
Vikas123
(
359
points)

53
views
cutoffs
engineeringmathematics
discretemathematics
graphtheory
0
votes
0
answers
23
VirtualGATE
Let G be a graph on n vertices with 4n16 edges. Consider the following: 1. There is a vertex of degree smaller than 8 in G. 2. There is a vertex such that there are less than 16 vertices at distance exactly 2 from it. Which of the following is TRUE: a) 1 only b) 2 only c) Both 1 and 2 d) neither.
asked
Jan 9
in
Algorithms
by
pps121
Active
(
1.5k
points)

56
views
virtualgate
graphtheory
0
votes
0
answers
24
Made_easy_test_series
The number of totally ordered sets compatible to the given POSET are ________.
asked
Jan 7
in
Graph Theory
by
Shivam Kasat
Active
(
1.9k
points)

141
views
discretemathematics
graphtheory
0
votes
0
answers
25
simple graph formula
why in this planar graph this theorem ,”sum of degrees of faces or regions is twice the number of edges” is not true as it should hold for all planar graphs?? Note: numbers denote region or face
asked
Jan 5
in
Graph Theory
by
BHASHKAR
(
21
points)

34
views
graphtheory
engineeringmathematics
discretemathematics
0
votes
0
answers
26
The maximum value of ‘n’ so that overflow cannot occur. Algorithms MeadEasy.
asked
Jan 3
in
Algorithms
by
susgir2
Active
(
1.4k
points)

51
views
graphtheory
algorithms
0
votes
0
answers
27
Eulerian Graph has to be connected?
A disconnected graph having even degree vertices can it be a euler graph?
asked
Jan 1
in
Graph Theory
by
sripo
Active
(
1.5k
points)

67
views
graphtheory
eulergraph
graphconnectivity
madeeasytestseries
0
votes
0
answers
28
What to study & from where to study  Graph Theory for GATE 2019.
Are the following topics necessary/ apt to study for gate.(Bold items are explicitly mentioned in gate syllabus document) Connectivity Matching Coloring Cuts Covering Independent Sets Planar Graphs Isomorphism Walks, Trails, Paths, ... taking a lot of time. Can anyone please recommend a reliable and simple resource to go with.
asked
Dec 29, 2018
in
Graph Theory
by
Krishna Sai Vootla
(
25
points)

87
views
syllabus
engineeringmathematics
graphtheory
graphplanarity
graphisomorphism
vertexcover
0
votes
0
answers
29
#graph
why DFS cannot find shortest path but BFS can?
asked
Dec 29, 2018
in
Algorithms
by
Deepesh Pai
(
499
points)

25
views
graphtheory
algorithms
discretemathematics
0
votes
1
answer
30
In a 3array tree if internal nodes have exactly 3 children,the number of leaf nodes will be __ ?
asked
Dec 25, 2018
in
DS
by
sripo
Active
(
1.5k
points)

99
views
binarytree
trees
graphtheory
algorithms
datastructure
Page:
1
2
3
4
5
6
...
20
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
Challenge to GATE keys: Question 26, If you also want to challenge the same, as I did!
How to follow Standard Textbooks?
Gate contest link is now open
Official keys are out now.
JEST 2019 MEMORY BASED QUESTION PAPER
Follow @csegate
Recent questions tagged graphtheory
Recent Blog Comments
Even I have challenged question number 50. Let us...
yes ,the answer will no doubt will be 3 NOR gates...
47,922
questions
52,324
answers
182,350
comments
67,780
users