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 tagged graphtheory
Webpage for Graph Theory:
+3
votes
7
answers
1
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
asked
Feb 14
in
Graph Theory
by
gatecse
Veteran
(
18k
points)

1.3k
views
gate2018
graphtheory
normal
+4
votes
3
answers
2
GATE201818
The chromatic number of the following graph is _____
asked
Feb 14
in
Graph Theory
by
gatecse
Veteran
(
18k
points)

938
views
gate2018
graphtheory
chromaticnumber
numericalanswers
0
votes
1
answer
3
Graph theory
If N=(0,1,2,3 ....) , then (N,+) is a Group. If N=(1,2,3 ....) , then (N,+) is a not Group. Which one to consider in exam ?
asked
Feb 6
in
Mathematical Logic
by
Aspirant
Loyal
(
2.9k
points)

88
views
graphtheory
discretemathematics
0
votes
1
answer
4
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.
asked
Feb 5
in
Graph Theory
by
Tesla!
Veteran
(
14.4k
points)

66
views
cmi2017
graphtheory
+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
asked
Feb 5
in
Graph Theory
by
Tesla!
Veteran
(
14.4k
points)

50
views
graphtheory
cmi2017
+1
vote
0
answers
6
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
7
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
8
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.
asked
Jan 27
in
Graph Theory
by
Tuhin Dutta
Boss
(
7.8k
points)

88
views
discretemathematics
graphtheory
+1
vote
0
answers
9
Difference between a walk and a path
asked
Jan 22
in
Algorithms
by
Balaji Jegan
Junior
(
865
points)

15
views
graphtheory
+3
votes
0
answers
10
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
11
ace test
I got 206???
asked
Jan 22
in
Algorithms
by
Deepak Mokili
(
363
points)

68
views
acetestseries
algorithms
dynamicprogramming
merging
graphtheory
optimalmergepattern
+1
vote
0
answers
12
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
13
Graph
I am getting 16X15/2=120 given is 105
asked
Jan 21
in
Graph Theory
by
Inspiron
Active
(
1.5k
points)

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

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

123
views
spanningtree
graphtheory
minimumspanningtrees
+2
votes
0
answers
16
graph
Is there any algorithm to find number of different minimum spanning trees for a graph?
asked
Jan 18
in
Mathematical Logic
by
raviyogi
Loyal
(
2.6k
points)

59
views
graphtheory
graphconnectivity
engineeringmathematics
+1
vote
0
answers
17
[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
+2
votes
0
answers
18
Hamiltonian Graph
A complement of a cyclic graph on 5 vertices , has an Hamiltonian circuit . (True/False)
asked
Jan 16
in
Mathematical Logic
by
VS
Boss
(
8k
points)

75
views
graphtheory
discretemathematics
+1
vote
0
answers
19
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
+5
votes
0
answers
20
Strongly connected component
asked
Jan 12
in
Graph Theory
by
Lakshman Patel RJIT
Boss
(
6.7k
points)

73
views
graphtheory
+5
votes
1
answer
21
Articulation point in graph
asked
Jan 12
in
Graph Theory
by
Lakshman Patel RJIT
Boss
(
6.7k
points)

40
views
graphtheory
+1
vote
0
answers
22
Graph
Consider the following statements: S1 : We might prefer FloydWarshall to BellmanFord when we want to find shortest path between all pair of vertices. S2 : We might prefer BellmanFord to Dijkstra's algorithm when graph have negative edge ... of the following statements are true? i think all statement are correct ,we can use bfs to find shortest distance?
asked
Jan 12
in
Algorithms
by
Nishtha3121996
(
293
points)

15
views
graphtheory
+2
votes
1
answer
23
madeeasy
answer given is 4. Please provide a detailed solution.
asked
Jan 12
in
Graph Theory
by
kapilbk1996
(
327
points)

64
views
graphtheory
madeeasytestseries
+1
vote
1
answer
24
doubt
someone post complete solution
asked
Jan 11
in
Algorithms
by
Prateek kumar
Veteran
(
10.4k
points)

40
views
graphtheory
+3
votes
0
answers
25
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
(
7.1k
points)

68
views
graphtheory
discretemathematics
graphconnectivity
graphcoloring
+2
votes
1
answer
26
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 __ .
asked
Jan 10
in
Graph Theory
by
Mk Utkarsh
Boss
(
7.1k
points)

59
views
graphtheory
discretemathematics
+2
votes
0
answers
27
Graph theory
How many simple graph are possible on six vertices in which the number of edge is odd??
asked
Jan 10
in
Mathematical Logic
by
akankshadewangan24
Loyal
(
4.8k
points)

95
views
graphtheory
+2
votes
1
answer
28
Degree of Graph
Consider the graph with 11 vertices and 16 edges. The maximum value of minimum degree of the graph is __________________
asked
Jan 9
in
Graph Theory
by
srestha
Veteran
(
81.5k
points)

95
views
graphtheory
discretemathematics
+2
votes
2
answers
29
Subgraph
Number of subgraphs possible for K3 =____________
asked
Jan 9
in
Graph Theory
by
srestha
Veteran
(
81.5k
points)

93
views
graphtheory
+2
votes
1
answer
30
gate forum test series
How to solve this question?
asked
Jan 8
in
Graph Theory
by
charul
Active
(
1.6k
points)

54
views
graphtheory
discretemathematics
Page:
1
2
3
4
5
6
...
15
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
isro sc 2017 2nd paper
Which college to expect?
Interview Guidance
CDAC CoursesAugust session
Counselling...
Follow @csegate
Gatecse
Recent questions tagged graphtheory
Recent Blog Comments
Sir , pls guide us how to prepare for the ...
Sir in Indian edition it is present
Okay Thanks
i think they call everyone ith a score higher ...
@raviyogi Do you know what was the cutoff ot IIT ...
33,720
questions
40,265
answers
114,392
comments
38,903
users