The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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:
+3
votes
1
answer
1
UGCNETJune2019II5
For which values of $m$ and $n$ does the complete bipartite graph $k_{m,n}$ have a Hamiltonian circuit ? $m\neq n,\ \ m,n \geq 2$ $m\neq n,\ \ m,n \geq 3$ $m=n,\ \ m,n \geq 2$ $m= n,\ \ m,n \geq 3$
asked
Jul 2
in
Graph Theory
by
Arjun
Veteran
(
418k
points)

100
views
ugcnetjune2019ii
graphtheory
0
votes
1
answer
2
Doubt on Bipartite Graph
What is T.C. to find maximum number of edges to be added to a tree so that it stays as a bipartite graph? Now my question is, why do we need to add edges to make a tree bipartite? A tree is already bipartite graph. Right?? Again how do we add edges in it?? Is BFS or DFS do any improvement in such a tree?? How to think such a question??
asked
Jun 2
in
Algorithms
by
srestha
Veteran
(
114k
points)

56
views
graphtheory
algorithms
+1
vote
1
answer
3
ACE ACADEMY BOOKLET
Which of the following is $\textbf{not}$ TRUE? (a) In a complete graph $K_n$ ($n$ $\geq$ $3$), Hamiltonian cycle exists for all n. (b) In a complete bipartite graph $K_{m,n}$ (m $\geq$ 2 and n $\geq$2), Hamiltonian cycle exists $\Leftrightarrow$ ... Hamiltonian cycle exits for all $n$ (d) In a wheel graph $W_n$ ($n \geq 4$), Hamiltonian cycle exits $\Leftrightarrow$ $n$ is even.
asked
May 26
in
Graph Theory
by
`JEET
Active
(
3.8k
points)

52
views
graphtheory
discretemathematics
+1
vote
2
answers
4
#ACE_ACADEMY_DISCRETE_MATHS_BOOKLET.
Which of the following is not true? (a) Number of edgedisjoint Hamiltonian cycles in $K_7$ is $3$ (b) If $G$ is a simple graph with $6$ vertices and the degree of each vertex is at least $3$, then the Hamiltonian cycle exists in ... simple graph with $5$ vertices and $7$ edges, then the Hamiltonian cycle exists in $G$ Please help me understand all the options.
asked
May 26
in
Graph Theory
by
`JEET
Active
(
3.8k
points)

88
views
discretemathematics
graphtheory
+1
vote
1
answer
5
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_{n1}$, 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_____________
asked
May 23
in
Graph Theory
by
srestha
Veteran
(
114k
points)

100
views
madeeasytestseries
graphtheory
theoryofcomputation
+4
votes
0
answers
6
IISc CSA  Research Interview Question
Prove that the rank of the Adjacency Matrix which is associated with a $k$ regular graph is $k.$
asked
May 22
in
Graph Theory
by
ankitgupta.1729
Boss
(
14.3k
points)

82
views
graphtheory
linearalgebra
+2
votes
2
answers
7
GateForum Question Bank :Graph Theory
What is the probability that there is an edge in an undirected random graph having 8 vertices? 1 1/8
asked
May 19
in
Graph Theory
by
Hirak
Active
(
3.4k
points)

120
views
graphtheory
discretemathematics
0
votes
2
answers
8
ACE Workbook:
ACE Workbook: Q) Let G be a simple graph(connected) with minimum number of edges. If G has n vertices with degree1,2 vertices of degree 2, 4 vertices of degree 3 and 3 vertices of degree4, then value of n is ? Can anyone give the answer and how to approach these problems. Thanks in advance.
asked
May 12
in
Graph Theory
by
chandan2teja
(
131
points)

78
views
graphtheory
0
votes
1
answer
9
IIIT PGEE 2019
Which of the following gives O(1) complexity if we want to check whether an edge exists between two given nodes in a graph? Adjacency List Adjacency Matrix Incidence Matrix None of these
asked
Apr 29
in
DS
by
manikgupta123
(
75
points)

125
views
iiithpgee
graphtheory
timecomplexity
+1
vote
0
answers
10
Difference between DAG and Multistage graph
I have trouble understanding the difference between DAG and Multistage graph. I know what each of them is But I think that a multistage graph is also a DAG. Are multistage graphs a special kind of DAG?
asked
Apr 28
in
Graph Theory
by
gmrishikumar
Active
(
1.9k
points)

63
views
graphtheory
graphalgorithms
graphconnectivity
multistagegraph
directedacyclicgraph
dag
0
votes
0
answers
11
ISI2017PCBB1(b)
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.
asked
Apr 8
in
Graph Theory
by
akash.dinkar12
Boss
(
41.4k
points)

43
views
isi2017pcbb
engineeringmathematics
discretemathematics
graphtheory
descriptive
0
votes
0
answers
12
Graph Decomposition
What is Graph Decomposition & is it in the syllabus? If it is then please can anyone share some online resources for it. Thank you.
asked
Mar 17
in
Graph Theory
by
noxevolution
(
93
points)

35
views
graphtheory
0
votes
0
answers
13
Narsingh deo
What is meant by edge disjoint hamiltonian circuits in a graph
asked
Mar 5
in
Graph Theory
by
Winner
(
283
points)

68
views
graphtheory
+1
vote
0
answers
14
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
Feb 18
in
Graph Theory
by
Sayan Bose
Loyal
(
7k
points)

90
views
jest
graphtheory
+5
votes
8
answers
15
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
(
418k
points)

3k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+3
votes
2
answers
16
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
(
418k
points)

2.6k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+1
vote
0
answers
17
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
(
417
points)

125
views
graphmatching
discretemathematics
graphtheory
testseries
0
votes
2
answers
18
#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
(
563
points)

99
views
graphtheory
0
votes
0
answers
19
Counting
asked
Jan 25
in
Graph Theory
by
screddy1313
(
455
points)

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

93
views
graphtheory
datastructure
0
votes
1
answer
21
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
(
279
points)

78
views
discretemathematics
graphtheory
testseries
0
votes
0
answers
22
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.1k
points)

45
views
graphisomorphism
graphtheory
groups
0
votes
1
answer
23
MadeEasy Test Series: Discrete Mathematics  Graph Thoery
The number of labelled subgraphs possible for the graph given below.
asked
Jan 19
in
Graph Theory
by
snaily16
(
245
points)

274
views
madeeasytestseries
discretemathematics
graphtheory
0
votes
0
answers
24
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
(
31
points)

29
views
graphtheory
0
votes
0
answers
25
Ace Test Series: Graph Theory  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
(
6.7k
points)

83
views
graphtheory
acetestseries
0
votes
1
answer
26
ME test series question on graph theory
asked
Jan 17
in
Graph Theory
by
Shankar Kakde
(
195
points)

74
views
graphtheory
+1
vote
2
answers
27
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
(
647
points)

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

51
views
graphtheory
madeeasytestseries
seelater
+1
vote
1
answer
29
MadeEasy Subject Test 2019: Graph Thoery  Graph Coloring
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
(
6.7k
points)

99
views
discretemathematics
graphtheory
madeeasytestseries2019
madeeasytestseries
+1
vote
1
answer
30
MadeEasy Full Length Test 2019: Graph Theory  Vertex Connectivity
The Vertex Connectivity of Graph is : 1 2 3 None
asked
Jan 16
in
Graph Theory
by
Na462
Loyal
(
6.7k
points)

113
views
graphtheory
graphconnectivity
madeeasytestseries2019
madeeasytestseries
Page:
1
2
3
4
5
6
...
21
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
GATE 2020 Application Form Opened!
My GATE Preparation Journey
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Follow @csegate
Recent questions tagged graphtheory
Recent Blog Comments
Feedback for next edition (if ever there's...
Is go book still available,I want to buy it
will pdfs be uploaded ?
6th...
49,896
questions
55,153
answers
190,576
comments
85,317
users