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
+33
votes
5
answers
1
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
2 days
ago
in
Graph Theory
by
Kuljeet Shan
Junior
(
657
points)

2.5k
views
gate2006it
graphtheory
graphcoloring
normal
0
votes
0
answers
2
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
5 days
ago
in
Graph Theory
by
noxevolution
(
73
points)

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

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

35
views
graphtheory
+1
vote
1
answer
5
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.3k
points)

314
views
graphtheory
discretemathematics
algorithms
+2
votes
1
answer
6
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)

127
views
0
votes
0
answers
7
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
(
5.9k
points)

51
views
jest
graphtheory
0
votes
0
answers
8
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
(
689
points)

56
views
jest
2019
discretemathematics
0
votes
0
answers
9
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
(
689
points)

35
views
jest
2019
discretemathematics
+12
votes
3
answers
10
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 of ... 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
(
5.3k
points)

580
views
cmi2013
graphtheory
normal
degreeofgraph
0
votes
4
answers
11
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
Feb 14
in
Graph Theory
by
OO7
Junior
(
579
points)

2.5k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+21
votes
8
answers
12
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
(
737
points)

4.2k
views
gate20172
graphtheory
numericalanswers
degreeofgraph
+1
vote
1
answer
13
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.5k
points)

2k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
0
votes
1
answer
14
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)

290
views
usergate2019
usermod
discretemathematics
graphtheory
0
votes
2
answers
15
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
(
793
points)

709
views
0
votes
0
answers
16
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)

35
views
0
votes
4
answers
17
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
(
149
points)

315
views
gateforumtestseries
engineeringmathematics
discretemathematics
graphtheory
graph
graphcoloring
0
votes
0
answers
18
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
(
343
points)

103
views
graphmatching
discretemathematics
graphtheory
testseries
0
votes
0
answers
19
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
(
3.2k
points)

25
views
0
votes
0
answers
20
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
Loyal
(
9.7k
points)

64
views
0
votes
1
answer
21
#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
Active
(
4.7k
points)

65
views
graphtheory
0
votes
0
answers
22
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)

74
views
mst
0
votes
0
answers
23
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
(
369
points)

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

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

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

46
views
0
votes
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$
answered
Jan 25
in
Graph Theory
by
Utkarsh Joshi
Loyal
(
7.2k
points)

85
views
appldcourse2019mock1
graphtheory
0
votes
0
answers
28
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.2k
points)

47
views
0
votes
1
answer
29
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?
answered
Jan 24
in
Graph Theory
by
Sushant Devkar
(
177
points)

67
views
discretemathematics
graphtheory
testseries
+1
vote
2
answers
30
GATEBOOK2019 Mock Test140
The number of graphs possible with $5$ vertices and $3$ edges is ____ $10$ $15$ $5$ $120$
answered
Jan 23
in
Graph Theory
by
gmrishikumar
Active
(
1.7k
points)

255
views
gb2019mock1
+1
vote
1
answer
31
GATEBOOK2019 Mock Test139
Consider the collection of all un directed graphs with $10$ nodes and $6$ edges. Let M and m, respectively, be the maximum and minimum number of connected components in any graph in the collection. If a graph has no self loops and there is at most one edge between any pair of nodes, which of the ... $M = 10, \: m = 1$ $M = 7, \: m = 4$ $M = 6, \: m = 4$
answered
Jan 23
in
Graph Theory
by
Ashwani Kumar 2
Boss
(
14.9k
points)

130
views
gb2019mock1
0
votes
2
answers
32
MadeEasy Test Series: Graph Theory
How to solve such problems?
answered
Jan 22
in
Graph Theory
by
royal shubham
Junior
(
557
points)

107
views
madeeasytestseries
discretemathematics
graphtheory
0
votes
2
answers
33
Suppose a connected graph has 15 labeled nodes
Suppose a connected graph has 15 labeled nodes, given that it has an eularian circuit, what is the minimum number of distinct circuits which it must have? [Note : the circuit a>b>c>a is not same as b>c>a>b]
answered
Jan 21
in
Graph Theory
by
abhigpt95
(
97
points)

206
views
graphtheory
0
votes
0
answers
34
SelfDoubt
Checking for Euler Path i.A graph has Euler path if exactly two vertices is of odd degree. if a graph have euler circuit=>all vertices even degree=>euler circuit which already cover euler path. am i correct? i is necessary and sufficient condition? So for ... check either 1.Euler Circuit or 2.Exactly two odd degree then it will have euler path but not euler circuit. is it correct?
[closed]
asked
Jan 20
in
Graph Theory
by
Abhisek Tiwari 4
Active
(
4.2k
points)

31
views
0
votes
1
answer
35
MadeEasy Test Series: Discrete Mathematics  Graph Thoery
The number of labelled subgraphs possible for the graph given below.
answered
Jan 20
in
Graph Theory
by
balchandar reddy san
Active
(
2.7k
points)

227
views
madeeasytestseries
discretemathematics
graphtheory
0
votes
0
answers
36
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
(
8.7k
points)

62
views
graphtheory
acetestseries
0
votes
0
answers
37
made easy adv mock
A graph G is self complementary iff G is isomorphoc to its complement.Let X be a self complementary graph.Which of the following is a viable possibility with regards to connectivity of X and X' ,where X' denotes the complement of X? a)both X and X' are ... X' is disconnected c)X' is connected and X' is disconnected d)both X and X' are connected ans is (d) pls explain
asked
Jan 18
in
Graph Theory
by
Gate Fever
Active
(
4.7k
points)

34
views
0
votes
1
answer
38
ME test series question on graph theory
answered
Jan 18
in
Graph Theory
by
Priyadrasta Raut
(
373
points)

58
views
graphtheory
+51
votes
7
answers
39
GATE2014151
Consider an undirected graph $G$ where selfloops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $ac \leq 1$ and $bd \leq 1$. The number of edges in this graph is______.
answered
Jan 17
in
Graph Theory
by
Apoorva Jain
(
455
points)

6.6k
views
gate20141
graphtheory
numericalanswers
normal
graphconnectivity
+1
vote
2
answers
40
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
answered
Jan 17
in
Graph Theory
by
muthu kumar
Active
(
1.5k
points)

67
views
discretemathematics
graphtheory
madeeasytestseries2019
madeeasytestseries
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 Gandhinagar review
AIR175 : GO is enough
GATE 2019 My reasoned routine. (AIR 558)
if i can you also can
M.S admissions help
All categories
General Aptitude
1.6k
Engineering Mathematics
7.3k
Discrete Mathematics
5k
Mathematical Logic
2.1k
Set Theory & Algebra
1.3k
Combinatory
876
Graph Theory
812
Probability
1k
Linear Algebra
693
Calculus
500
Digital Logic
2.7k
Programming & DS
4.9k
Algorithms
4.2k
Theory of Computation
5.4k
Compiler Design
2.1k
Operating System
4.2k
Databases
4k
CO & Architecture
3.5k
Computer Networks
4.2k
Non GATE
1.4k
Others
1.5k
Admissions
570
Exam Queries
566
Tier 1 Placement Questions
23
Job Queries
70
Projects
18
Follow @csegate
Recent questions and answers in Graph Theory
Recent Blog Comments
can anybody compare it with other new iits such...
can i get a call on 580 (OBCNCL)
Many times Anger , Aggression and Fear push...
One word would be "Priorities" Second word shall...
What's interesting to me is that despite having...
48,691
questions
52,776
answers
183,434
comments
68,389
users