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 and answers in Graph Theory
+1
vote
1
answer
1
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
answered
May 20
in
Graph Theory
by
srestha
Veteran
(
114k
points)

53
views
graphtheory
discretemathematics
+1
vote
2
answers
2
CMI2011B01b
A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that: Each road connects exactly two buildings. Any two buildings are connected via a sequence of roads. ... preferred roads differing in at least one road? Substantiate your answers by either proving the assertion or providing a counterexample.
answered
May 19
in
Graph Theory
by
Arjun
Veteran
(
400k
points)

121
views
cmi2011
descriptive
graphtheory
graphconnectivity
+1
vote
2
answers
3
GATE19894vii
Provide short answers to the following questions: In the graph shown above, the depthfirst spanning tree edges are marked with a 'T'. Identify the forward, backward and cross edges.
answered
May 18
in
Graph Theory
by
Arjun
Veteran
(
400k
points)

258
views
gate1989
descriptive
graphtheory
spanningtree
0
votes
1
answer
4
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.
answered
May 17
in
Graph Theory
by
pdeshal
(
11
points)

41
views
graphtheory
0
votes
0
answers
5
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.8k
points)

41
views
graphtheory
graphalgorithms
graphconnectivity
multistagegraph
directedacyclicgraph
dag
+1
vote
7
answers
6
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}$
answered
Apr 26
in
Graph Theory
by
gaurav1.yuva
(
403
points)

2.7k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
0
votes
0
answers
7
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
(
40.5k
points)

27
views
isi2017pcbb
engineeringmathematics
discretemathematics
graphtheory
descriptive
0
votes
0
answers
8
selfdoubt
A graph with alternating edges and vertices is called a walk (we can repeat the number of vertices and edges any number of times) . A walk in which no edges are repeated is called a trial. A trial in which no vertices are repeated is called a path. A trial in which only the starting and ending vertices are repeated is called a circuit. Are the definitions correct??
asked
Mar 31
in
Graph Theory
by
Doraemon
(
203
points)

13
views
graph
0
votes
0
answers
9
self doubt
What is the general formula for number of simple graph having n unlabelled vertices ??
asked
Mar 31
in
Graph Theory
by
Doraemon
(
203
points)

34
views
simplegraph
+18
votes
5
answers
10
TIFR2010B36
In a directed graph, every vertex has exactly seven edges coming in. What can one always say about the number of edges going out of its vertices? Exactly seven edges leave every vertex. Exactly seven edges leave some vertex. Some vertex has at least seven edges leaving it. The number of edges coming out of vertex is odd. None of the above.
answered
Mar 29
in
Graph Theory
by
Debargha Bhattacharj
(
225
points)

1k
views
tifr2010
graphtheory
degreeofgraph
0
votes
1
answer
11
Allen Career Institute: Spanning tree
Let $G$ be a simple undirected complete and weighted graph with vertex set $V = {0, 1, 2, . 99.}$ Weight of the edge $(u, v)$ is $\left  uv \right $ where $0\leq u, v\leq 99$ and $u\neq v$. Weight ... tree is______________ Doubt:Here asking for maximum weight spanning tree. So, there weight will be $0$ to every node. Isnot it? but answer given 7351.
answered
Mar 29
in
Graph Theory
by
ankitgupta.1729
Boss
(
11.3k
points)

66
views
discretemathematics
0
votes
1
answer
12
Allen Career Institute:Graph Theory
If G be connected planar graph with 12 vertices of deg 4 each. In how many regions can this planar graph be partitioned?
answered
Mar 28
in
Graph Theory
by
abhishekmehta4u
Boss
(
33.6k
points)

47
views
discretemathematics
+32
votes
6
answers
13
GATE2014351
If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have? $\left\lfloor\frac {n}{k}\right\rfloor$ $\left\lceil \frac{n}{k} \right\rceil$ $nk$ $nk+1$
answered
Mar 27
in
Graph Theory
by
Ashish Kumar Choubey
(
35
points)

4.1k
views
gate20143
graphtheory
graphconnectivity
normal
+33
votes
5
answers
14
GATE2006IT25
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by flipping a single ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$
answered
Mar 20
in
Graph Theory
by
Kuljeet Shan
Active
(
1.3k
points)

2.6k
views
gate2006it
graphtheory
graphcoloring
normal
0
votes
0
answers
15
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
(
103
points)

26
views
graphtheory
+1
vote
1
answer
16
Zeal Test Series 2019: Graph Theory  Graph Matching
answered
Mar 7
in
Graph Theory
by
abhishekmehta4u
Boss
(
33.6k
points)

68
views
zeal
discretemathematics
graphtheory
graphmatching
zeal2019
0
votes
0
answers
17
Narsingh deo
What is meant by edge disjoint hamiltonian circuits in a graph
asked
Mar 5
in
Graph Theory
by
Winner
(
269
points)

49
views
graphtheory
+1
vote
1
answer
18
Strongly Connected, Unilaterally connected and weakly Connected
Hi Guys, Is there any quick way of verifying Graph is Strongly Connected, Unilaterally connected and weakly Connected ? For Example  If 1 dead point then graph is Unilaterally Connected and If 2 dead points then graph is Weakly Connected.
answered
Feb 22
in
Graph Theory
by
saurav raghaw
Active
(
1.4k
points)

433
views
graphtheory
discretemathematics
algorithms
+2
votes
1
answer
19
GATE  2014  1 51 modified
Consider an directed graph G where selfloops are not allowed. The vertex set of G is {(i,j)∣1≤i≤12,1≤j≤12}There is an edge from(a,b) to (c,d) if a−c≤1 and b−d≤1. The number of edges in this graph is______
answered
Feb 18
in
Graph Theory
by
Priyadrasta Raut
(
373
points)

132
views
0
votes
0
answers
20
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
(
6.9k
points)

69
views
jest
graphtheory
0
votes
0
answers
21
JEST 2019 Descriptive Q2 (8 Marks)
Given a sequence $a_1$, $a_2$ , $a_3$ ... $a_n$ of any different positive integers, exhibit an arrangement of integers between 1 and $n^2$ which has no increasing or decreasing subsequence of length n+1.
asked
Feb 17
in
Graph Theory
by
dan31
Junior
(
877
points)

72
views
jest
2019
discretemathematics
0
votes
0
answers
22
JEST 2019 Descriptive Q1 (8 Marks)
Suppose that G contains a cycle C, and a path of length at least k between some two vertices of C. Show that G contains a cycle of length at least √k.
asked
Feb 17
in
Graph Theory
by
dan31
Junior
(
877
points)

48
views
jest
2019
discretemathematics
+12
votes
3
answers
23
CMI2013A06
A simple graph is one in which there are no selfloops 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 ... degree $6$ and a vertex of degree $7$. Which of the following can be the degree of the last vertex? $3$ $0$ $5$ $4$
answered
Feb 15
in
Graph Theory
by
Satbir
Loyal
(
7.5k
points)

616
views
cmi2013
graphtheory
normal
degreeofgraph
+21
votes
8
answers
24
GATE2017223
$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .
answered
Feb 8
in
Graph Theory
by
Suneel Padala
Junior
(
841
points)

4.3k
views
gate20172
graphtheory
numericalanswers
degreeofgraph
+1
vote
1
answer
25
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
answered
Feb 7
in
Graph Theory
by
Digvijay Pandey
Veteran
(
59.7k
points)

2.3k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
0
votes
1
answer
26
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!
answered
Feb 7
in
Graph Theory
by
Sahil Arora 2
(
15
points)

324
views
usergate2019
usermod
discretemathematics
graphtheory
0
votes
2
answers
27
GATE2019
What is the total number of different Hamiltonian cycles for the complete graph of n vertices?
answered
Feb 3
in
Graph Theory
by
Sumit Rana 1
Junior
(
819
points)

728
views
0
votes
0
answers
28
Abelian group
A quick question Is every multiplication modulo function a Abelian group....Or is it the case that the function should have prime number as modulo
asked
Feb 2
in
Graph Theory
by
Nandkishor3939
Active
(
1.2k
points)

36
views
0
votes
4
answers
29
GateForum Test Series: Graph Theory  Graph Coloring
The Chromatic Number of Cycle Graph with 7 vertices _____
answered
Feb 1
in
Graph Theory
by
Sai Shravan
(
169
points)

342
views
gateforumtestseries
engineeringmathematics
discretemathematics
graphtheory
graph
graphcoloring
0
votes
0
answers
30
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
(
423
points)

112
views
graphmatching
discretemathematics
graphtheory
testseries
0
votes
0
answers
31
Madeeasy
A graph G is called self complementary iff G is isomorphic to its complement. Let X be a self complementary graph. Which of the following is a viable possibility with regards to the connectivity of X and X', where X' denotes the complement of X, ... answer such questions. So the conclusion is "Every sell complementary graph is cormected". So option (d) is the correct answer.
asked
Jan 29
in
Graph Theory
by
mehul vaidya
Active
(
4.4k
points)

26
views
0
votes
0
answers
32
selfdoubtMEtestseries
we define a new measure ,called GoldIndex(G,C).it takes two arguments as input namely a graph G and set of colors C respectively . the subroutine outputs an integer denoting the number of ways assigning colors to vertices in G such that at least two vertices ... 't know where m i going wrong ,please help me i know their solution is correct but i want to verify my approach
[closed]
asked
Jan 29
in
Graph Theory
by
Prateek Raghuvanshi
Boss
(
10.2k
points)

65
views
0
votes
1
answer
33
#GRAPH THEORY
A simple regular graph n vertices and 24 edges, find all possible values of n.
answered
Jan 29
in
Graph Theory
by
prashant jha 1
Loyal
(
5.4k
points)

71
views
graphtheory
0
votes
0
answers
34
max weighted MST possible
Let G be a complete undirected graph on 5 vertices 10 edges, with weights being 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Let X be the value of the maximum possible weight a MST of G can have. Then the value of x will be_____ the answer to this question is given as 11 but there is no procedure given . Please ,can anyone help me out in understanding the procedure
asked
Jan 26
in
Graph Theory
by
Nandkishor3939
Active
(
1.2k
points)

84
views
mst
0
votes
0
answers
35
Made Easy Practice Book
The number of labelled subgraph possible for the graph given below are ________.
asked
Jan 25
in
Graph Theory
by
Shankar Kakde
(
373
points)

36
views
0
votes
1
answer
36
ACE TEST SERIES QUESTION ON Graph Theory
answered
Jan 25
in
Graph Theory
by
soubhik baral
(
229
points)

41
views
0
votes
0
answers
37
Counting
asked
Jan 25
in
Graph Theory
by
screddy1313
(
477
points)

42
views
discretemathematics
graphtheory
engineeringmathematics
chromaticnumbers
#counting
0
votes
1
answer
38
ACE Test series question on Chromatic number
answered
Jan 25
in
Graph Theory
by
Sai Shravan
(
169
points)

50
views
0
votes
2
answers
39
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$
answered
Jan 25
in
Graph Theory
by
Utkarsh Joshi
Loyal
(
7.6k
points)

89
views
appldcourse2019mock1
graphtheory
0
votes
0
answers
40
SelfDoubt
A graph with each vertex has even degree contain Hamiltonian Cycle. True/False plz explain how to ensure Hamiltonian Cycle.
asked
Jan 25
in
Graph Theory
by
Abhisek Tiwari 4
Active
(
4.7k
points)

51
views
To see more, click for all the
questions in this category
.
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 Kanpur MS Interview experience
My GATE preparation and what you can learn from it
IIT Bombay RA (2019) Programming Questions
COAP Round 1 has started
MTECH (COUURSE WORK) AI INTERVIEW EXPERIENCE 2019
All categories
General Aptitude
1.7k
Engineering Mathematics
7.4k
Discrete Mathematics
5.2k
Mathematical Logic
2.1k
Set Theory & Algebra
1.4k
Combinatory
898
Graph Theory
801
Probability
989
Linear Algebra
686
Calculus
497
Digital Logic
2.9k
Programming & DS
4.9k
Algorithms
4.3k
Theory of Computation
6k
Compiler Design
2k
Operating System
4.2k
Databases
4.1k
CO & Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.4k
Others
1.6k
Admissions
591
Exam Queries
643
Tier 1 Placement Questions
23
Job Queries
72
Projects
23
Follow @csegate
Recent questions and answers in Graph Theory
Recent Blog Comments
It was free when I gave them, maybe they made it...
The tests are there but it ain't free. Cost is...
They removed their tests recently, I think it'll...
how did you get Success gateway test series for...
49,781
questions
53,593
answers
185,825
comments
70,880
users