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
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
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.
Recent questions and answers in Graph Theory
0
votes
0
answers
1
Graph theory
What is unorderd and ordered (if any) cycles in a given graph?
asked
Feb 16
in
Graph Theory
by
Sidd_
(
113
points)

32
views
+3
votes
7
answers
2
GATE201830
Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ ... \mid =1$. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II
answered
Feb 16
in
Graph Theory
by
suraj
Boss
(
5.7k
points)

1.3k
views
gate2018
graphtheory
normal
+4
votes
3
answers
3
GATE201818
The chromatic number of the following graph is _____
answered
Feb 14
in
Graph Theory
by
Syedarshadali
(
359
points)

935
views
gate2018
graphtheory
chromaticnumber
numericalanswers
0
votes
1
answer
4
discrete maths
How many ordered pair of integers (a, b) are needed to guarantee that there are two ordered pairs (a1, b1) and (a2, b1) such that a1 mod 5 = a2 mod 5 and b1 mod 5 = b2 mod 5? should not answer be 25 here
answered
Feb 13
in
Graph Theory
by
Ayush Upadhyaya
Boss
(
7.4k
points)

47
views
+1
vote
1
answer
5
CMI2017A05
Let G be an arbitrary graph on n vertices with 4n − 16 edges. Consider the following statements: I There is a vertex of degree smaller than 8 in G. II 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) I only (c) Both I and II (b) II only (d) Neither I nor II
answered
Feb 10
in
Graph Theory
by
Sourajit25
Junior
(
583
points)

50
views
graphtheory
cmi2017
0
votes
1
answer
6
CMI2017B5
An undirected graph is connected if, for any two vertices {u, v} of the graph, there is a path in the graph starting at u and ending at v. A tree is a connected, undirected graph that contains no cycle. (a) A leaf in a tree is a vertex that has ... , u ∈ V1 and v ∈ V2 or vice versa. Prove that if G is a tree with at least two vertices, then G is bipartite.
answered
Feb 6
in
Graph Theory
by
Yash Khanna
(
161
points)

66
views
cmi2017
graphtheory
0
votes
1
answer
7
CMI2017A04
City authorities are concerned about traffic accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of any accident along these roads. To minimize response time, ambulances are to be ... Find a spanning tree with minimum (c) Find a minimal coloring. (d) Find a minimum size vertex cover.
answered
Feb 5
in
Graph Theory
by
Tesla!
Veteran
(
14.4k
points)

36
views
algorithms
graphalgorithms
cmi2017
0
votes
1
answer
8
Spanning tree
How to approach such questions ? Please provide detailed solution. Answer given is option C
answered
Feb 2
in
Graph Theory
by
Mk Utkarsh
Boss
(
7k
points)

113
views
minimumspanningtrees
graphalgorithms
acetestseries
0
votes
1
answer
9
discrete maths
What is the coefficient of x^(12) in the power series of
answered
Feb 2
in
Graph Theory
by
Pawan Kumar 2
Boss
(
5.1k
points)

88
views
0
votes
1
answer
10
discrete maths
Consider the following statements: S1: Every cyclic group is Abelian group. S2: Every Abelian group is cyclic group. S3: Cyclic group of order 10 have 4 generators. Which of the following is true?
answered
Feb 1
in
Graph Theory
by
Raveena Yadav 1
Junior
(
775
points)

48
views
0
votes
1
answer
11
Test series
Plz explain ??
answered
Feb 1
in
Graph Theory
by
Raveena Yadav 1
Junior
(
775
points)

42
views
+1
vote
0
answers
12
Test series
my doubt is why 14 has been subtracted ??
asked
Feb 1
in
Graph Theory
by
Manis
Active
(
1.2k
points)

34
views
–1
vote
0
answers
13
#testseries
i got 5 and 4 but given ans is 6 and 6. How??
asked
Jan 30
in
Graph Theory
by
Sukhdip Singh
(
245
points)

42
views
madeeasytestseries
0
votes
1
answer
14
non abelian
Let G be a non abelian group, order of G can be 24 44 54 34
answered
Jan 30
in
Graph Theory
by
akshat sharma
Active
(
1.1k
points)

25
views
+1
vote
0
answers
15
Independence set and vertex cover
asked
Jan 29
in
Graph Theory
by
Hemant Parihar
Veteran
(
15k
points)

46
views
graphtheory
madeeasytestseries
+1
vote
0
answers
16
True or False
Even cycles are bipartite. true or false? and why?
asked
Jan 28
in
Graph Theory
by
adactive18
Junior
(
703
points)

47
views
discretemathematics

graphtheory
+1
vote
1
answer
17
Graph Theory vertex degree
Consider an undirected graph with n vertices, vertex 1 has degree 1, while each vertex 2,3......, n  1 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 the edge connecting vertex 1 and n.
answered
Jan 28
in
Graph Theory
by
Abhishek Kumar Singh
Active
(
1.2k
points)

88
views
discretemathematics
graphtheory
0
votes
1
answer
18
if the simple graph G has 5 vertices and 7 edges, how many edges does G have ?
answered
Jan 27
in
Graph Theory
by
Salazar
Junior
(
853
points)

64
views
+2
votes
0
answers
19
True/False
Which of the following statements related to graphs are True? Minimum Spanning Tree has ALWAYS Minimum weight edge included in it. Minimum Spanning Tree MIGHT have Maximum weight edge weight included in it. Maximum Spanning Tree has ALWAYS Maximum ... in it. Longest path from source to destination MAY OR MAY NOT have Maximum weight edge included in it.
asked
Jan 27
in
Graph Theory
by
Balaji Jegan
Junior
(
865
points)

28
views
graphs
graphalgorithms
algorithms
+2
votes
0
answers
20
gatebook
how they are drawing DAG.Can someone explain?
asked
Jan 26
in
Graph Theory
by
Niharika 1
Loyal
(
2.5k
points)

25
views
+3
votes
0
answers
21
TIFR GS 2018
. 9. How many ways are there to assign colors from the range {1, 2, . . . , r} to the vertices of the following graph so that adjacent vertices receive distinct colors? (a) r^4 (b) r^4 − 4r^3 (c) r^4 − 5r^3 + 8r^2 − 4r (d) r^4 − 4r^3 + 9r^2 − 3r (e) r^4 − 5r^3 + 10r^2 − 15r
[closed]
asked
Jan 24
in
Graph Theory
by
Lakshman Patel RJIT
Boss
(
6.5k
points)

55
views
tifr2018
0
votes
2
answers
22
Planar graph
The total number of planar graphs can be formed with 5 vertices are _____
answered
Jan 24
in
Graph Theory
by
sampathirao suneetha
(
11
points)

168
views
graphtheory
+3
votes
0
answers
23
Graph Coloring
A vertex colouring with four colours of a graph G = (V, E) is a mapping V → {R, G, B, Y }. So that any two adjacent vertices does not same colour. Consider the below graphs: The number of vertex colouring possible with 4 ... D with also blue which is other than Green, now this case is clearly violating graph coloring property. How, to solve this one?
asked
Jan 22
in
Graph Theory
by
Shubhanshu
Veteran
(
15.8k
points)

62
views
graphtheory
graphcoloring
+1
vote
0
answers
24
what is min degree ?
A graph G=(V,E)satisfies E≤3v6, the min degree of G is defined asmin{degree(v) } v∈V. Therefore min degree of ‘G’ can be ?
asked
Jan 21
in
Graph Theory
by
MIRIYALA JEEVAN KUMA
Active
(
1.5k
points)

37
views
graphtheory
+2
votes
1
answer
25
Graph
I am getting 16X15/2=120 given is 105
answered
Jan 21
in
Graph Theory
by
abhay nanda
(
149
points)

31
views
graphtheory
+1
vote
1
answer
26
[Ace Test Series] Graphs
my answer is C but the answer given is A someone please explain
answered
Jan 20
in
Graph Theory
by
Neeraj Chandrakar
Active
(
1.3k
points)

44
views
acetestseries
graphtheory
0
votes
1
answer
27
Graph
Suppose G is a connected planar simple graph having V vertices, E edges . Let R denote number of bounded regions, in a planar representation of G. Which of the following correct representation of E, V, R? 1) EV+R=1 2) VE+R=1 3) EV+R=2 4) VE+R=2
answered
Jan 18
in
Graph Theory
by
Shubham Pandey 2
Boss
(
7.2k
points)

71
views
graphtheory
discretemathematics
+2
votes
0
answers
28
Number of minimum spanning trees
asked
Jan 18
in
Graph Theory
by
vishal chugh
Active
(
1.5k
points)

123
views
spanningtree
graphtheory
minimumspanningtrees
+1
vote
0
answers
29
[Ace Test Series] Graphs
My answer 31 (graph can be linear) Answer given is 9. please explain why 31 is wrong :(
asked
Jan 17
in
Graph Theory
by
ashish pal
Active
(
1.3k
points)

76
views
acetestseries
graphtheory
+1
vote
0
answers
30
Graph theory
Since , matching no. + edge cover = no. of vertices= 1 +5 =6 Did I do right or wrong ?
asked
Jan 16
in
Graph Theory
by
Pawan Kumar 2
Boss
(
5.1k
points)

59
views
graphtheory
+1
vote
0
answers
31
Test Series
The binary operation defined on a,b∈z such that a*b= min(a,b)then (A,*) is 1.Monoid 2.Algebra structure 3.Group 4.Semi group
asked
Jan 16
in
Graph Theory
by
ankit_thawal
Loyal
(
2.5k
points)

38
views
engineeringmathematics
+2
votes
0
answers
32
DFS Depth First Search
If we backtrack in DFS ,then doesn't statement 1 becomes true ?
asked
Jan 14
in
Graph Theory
by
Pawan Kumar 2
Boss
(
5.1k
points)

49
views
dfs
+3
votes
2
answers
33
Counting number of articulation points
answered
Jan 13
in
Graph Theory
by
Sandeep Suri
Loyal
(
4.8k
points)

138
views
graphtheory
engineeringmathematics
+5
votes
1
answer
34
Articulation point in graph
answered
Jan 13
in
Graph Theory
by
Sandeep Suri
Loyal
(
4.8k
points)

40
views
graphtheory
+5
votes
0
answers
35
Strongly connected component
asked
Jan 12
in
Graph Theory
by
Lakshman Patel RJIT
Boss
(
6.5k
points)

73
views
graphtheory
+2
votes
2
answers
36
Subgraph
Number of subgraphs possible for K3 =____________
answered
Jan 12
in
Graph Theory
by
Sandeep Suri
Loyal
(
4.8k
points)

93
views
graphtheory
+2
votes
1
answer
37
madeeasy
answer given is 4. Please provide a detailed solution.
answered
Jan 12
in
Graph Theory
by
thepeeyoosh
Active
(
2.2k
points)

64
views
graphtheory
madeeasytestseries
+15
votes
2
answers
38
GATE2012_17
Let $G$ be a simple undirected planar graph on $10$ vertices with $15$ edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the plane is equal to (A) 3 (B) 4 (C) 5 (D) 6
answered
Jan 11
in
Graph Theory
by
w4rb0y
(
53
points)

1.6k
views
gate2012
graphtheory
graphplanarity
normal
outofsyllabusnow
+3
votes
0
answers
39
Graph Colouring
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is
asked
Jan 10
in
Graph Theory
by
Mk Utkarsh
Boss
(
7k
points)

68
views
graphtheory
discretemathematics
graphconnectivity
graphcoloring
+2
votes
1
answer
40
Degree of graph
There is a simple graph with 65 edges containing vertices of degree 2,3 and 4. In which vertices with degree 3 are twice the number of vertices with degree 4 and there are 10 vertices with degree 2. Number of vertices containing degree 3 and 4 are ___ and __ .
answered
Jan 10
in
Graph Theory
by
abhishek tiwary
Loyal
(
3.7k
points)

59
views
graphtheory
discretemathematics
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
Members at the site
Yash Khanna
NEETI PRIYA 1
Recent Posts
isro sc 2017 2nd paper
Which college to expect?
Interview Guidance
CDAC CoursesAugust session
Counselling...
All categories
General Aptitude
1.2k
Engineering Mathematics
4.7k
Discrete Mathematics
3.3k
Mathematical Logic
1.3k
Set Theory & Algebra
871
Combinatory
582
Graph Theory
555
Probability
600
Linear Algebra
473
Calculus
359
Digital Logic
1.9k
Programming & DS
3.5k
Algorithms
3k
Theory of Computation
3.7k
Compiler Design
1.5k
Operating System
2.7k
Databases
2.8k
CO & Architecture
2.5k
Computer Networks
2.9k
Non GATE
837
Others
1.2k
Admissions
281
Exam Queries
397
Tier 1 Placement Questions
17
Job Queries
51
Projects
7
Follow @csegate
Gatecse
Recent questions and answers in Graph Theory
Recent Blog Comments
@raviyogi Do you know what was the cutoff ot IIT ...
I think the exam has not yet been created.
Then why it's not appearing as a separate exam in ...
very low chances for top nits even in nsr round
okay. What about top NITs?
33,700
questions
40,250
answers
114,331
comments
38,858
users