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. For hardcopy of previous year questions please see
here
Recent questions tagged graphtheory
Webpage for Graph Theory:
0
votes
1
answer
1
Made Easy algorithms
How many edge disjoint spanning trees are possible for a undirected complete connected graph of n vertices?
asked
5 days
ago
in
Algorithms
by
Sambhrant Maurya
Junior
(
609
points)

26
views
algorithms
spanningtree
graphtheory
0
votes
2
answers
2
Graph theory Modified
What is the maximum integer value m such that every simple connected graph with r vertices and r+2 edges contains at least m different spanning trees ? 1)1 2)4 3)8 4)m
asked
5 days
ago
in
Graph Theory
by
srestha
Veteran
(
92k
points)

125
views
graphtheory
discretemathematics
0
votes
1
answer
3
Test Datasructures
Statement I : If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 Backedge Statement II : A graph G has a cycle if DFS finds at least 1 Backedge Which of the following option is correct ? ... option is correct(Statement 1 is false and Statement 2 is true but answer given is 1, please tell me where i am making mistake.
asked
Aug 11
in
Algorithms
by
Prince Sindhiya
Active
(
1.9k
points)

12
views
graphtheory
0
votes
0
answers
4
Show that T is a maximum spanning tree for G
asked
Jul 24
in
Graph Theory
by
abram19000
(
7
points)

25
views
graphtheory
graphalgorithms
0
votes
1
answer
5
ACE Bits and bYtes
Minimum no of edges necessary in a simple graph with 10 vertices to ensure connectivity is_______.
asked
Jul 24
in
Graph Theory
by
abhishek1995_cse
(
27
points)

64
views
graphtheory
graphconnectivity
+1
vote
1
answer
6
ACE Bits And Bytes
Number of perfect matching in Wn (n>=4 and n is even) _________.
asked
Jul 24
in
Graph Theory
by
abhishek1995_cse
(
27
points)

26
views
graphtheory
graphmatching
gate2019
0
votes
1
answer
7
me test
A simple graph with n vertices is constructed by randomly and independently placing an edge between every two vertices with probability p. What is the expected no. of nodes with degree 2?
asked
Jul 17
in
Graph Theory
by
ronin_codex
(
7
points)

31
views
probability
graphtheory
expectation
simplegraph
0
votes
0
answers
8
graph theory
10.A graph G has any two vertices connected by exactly one path. Find the Number of ways we can properly colour G it we are provided with 10 colours.
asked
Jul 14
in
Graph Theory
by
poojasharma123
(
81
points)

75
views
graphtheory
0
votes
0
answers
9
Gate 2018 Qn. 43
Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2,…,100. There is an edge between vertices and if and only if the label of can be obtained by swapping two adjacent numbers in the label of . Let denote the degree of a vertex in G, and denote the number of connected components in G. Then, y + 10z = _____.
asked
Jul 6
in
Graph Theory
by
Optimus Prime
(
425
points)

35
views
graphtheory
+1
vote
0
answers
10
Cormen 3rd edition chapter 22 question: 22.4.4
asked
Jul 4
in
Algorithms
by
Abhilash Mishra
(
85
points)

73
views
algorithms
graphtheory
graphalgorithms
topologicalsort
graphs
0
votes
2
answers
11
self doubt
Is it necessary that euler graph should always be simple graph?
asked
Jun 27
in
Graph Theory
by
Vegeta
(
187
points)

48
views
discretemathematics
graphtheory
0
votes
0
answers
12
Kenneth rosen
How many nonisomorphic directed graphs are there with $n$ vertices when $n$ is $2$ $3$ $4$
asked
Jun 18
in
Graph Theory
by
swati96
(
37
points)

29
views
engineeringmathematics
discretemathematics
kennethrosen
graphtheory
0
votes
0
answers
13
Kenneth rosen
How many nonisomorphic graphs are there with six vertices and four edges?
asked
Jun 18
in
Graph Theory
by
swati96
(
37
points)

12
views
engineeringmathematics
discretemathematics
graphtheory
0
votes
0
answers
14
Graphs, kenneth rosen
How many nonisomorphic simple graphs are there with five vertices and three edges?
asked
Jun 18
in
Graph Theory
by
swati96
(
37
points)

16
views
engineeringmathematics
discretemathematics
kennethrosen
graphtheory
0
votes
0
answers
15
Graphs, kenneth rosen
How many nonisomorphic simple graphs are there with five vertices and three edges?
asked
Jun 18
in
Graph Theory
by
swati96
(
37
points)

12
views
engineeringmathematics
discretemathematics
graphtheory
0
votes
1
answer
16
spanning tree
How we get maximum no. of spanning tree for give $n$ node is $n^{(n2)}$
asked
Jun 18
in
Graph Theory
by
piya
(
191
points)

26
views
engineeringmathematics
discretemathematics
graphtheory
0
votes
1
answer
17
True/False
Which of the following statements related to graphs are True? Consider a graph with Positive distinct edges 1.If we add a Positive Integer to all edges, then there are chances to get more than one shortest paths between 2 vertices 2.If we add a Positive Integer ... 4.If we add a Negative Integer to all edges, then there are chances to get more than one longest paths between 2 vertices
asked
Jun 9
in
Graph Theory
by
Balaji Jegan
Active
(
1.4k
points)

55
views
algorithms
graphtheory
djikstra
0
votes
0
answers
18
[414]Connectivity Narsingh Deo
Show that a simple graph is nonseparable iff for any two given arbitrary edges a circuit can always be found that will include these two edges.
asked
Jun 8
in
Graph Theory
by
Ayush Upadhyaya
Boss
(
11k
points)

32
views
graphtheory
narsinghdeo
0
votes
0
answers
19
[413]ConnectivityNarsingh Deo
Show that a graph G is nonseparable iff every vertex pair can be placed in some circuit in G.
asked
Jun 8
in
Graph Theory
by
Ayush Upadhyaya
Boss
(
11k
points)

15
views
graphtheory
narsinghdeo
0
votes
2
answers
20
SelfDoubt regarding Graph Coloring
This has reference to the below question https://gateoverflow.in/204092/gate201818?show=204092#q204092 My doubt is Suppose, I try to colour the vertices of this graph as follows First I colour vertex a and f with colour 1. Then I colour vertex e ... what points in mind do I need to remember so that I can colour any given graph with the minimum number of colours.
asked
Jun 7
in
Graph Theory
by
Ayush Upadhyaya
Boss
(
11k
points)

78
views
graphtheory
graphcoloring
0
votes
0
answers
21
Number of distinct cycles of length 4 in a complete graph of 6 labelled vertices.
asked
Jun 6
in
Graph Theory
by
Ayush Upadhyaya
Boss
(
11k
points)

62
views
graphtheory
engineeringmathematics
0
votes
2
answers
22
Number of Subgraphs of Kn?
I was searching for this question and found below link How many subgraphs does $K_5$ have? Here, in general, it is given to be $\displaystyle\sum_{r=0}^{n}\binom{n}{r}2^{\frac{r(r1)}{2}}$ My doubt is that the case for $r=0$ is taken if we select none of the vertices of $K_n$? Why the case for $ r=0$ considered?
asked
Jun 5
in
Graph Theory
by
Ayush Upadhyaya
Boss
(
11k
points)

41
views
engineeringmathematics
graphtheory
0
votes
2
answers
23
Connectivity(420) Narsingh Deo
Is every regular graph of degree d(d$\geq$3) nonseparable?If not, give a simple regular graph of degree 3 that is separable.
asked
Jun 2
in
Graph Theory
by
Ayush Upadhyaya
Boss
(
11k
points)

71
views
graphtheory
deo
narsingh
0
votes
0
answers
24
Connectivity(410)Narsingh Deo
Prove that in a connected graph G a vertex v is a cutvertex if and only if there exist two(or more) edges x and y incident on v such that no circuit in G includes both x and y.
asked
Jun 2
in
Graph Theory
by
Ayush Upadhyaya
Boss
(
11k
points)

38
views
graphtheory
narsingh
deo
0
votes
0
answers
25
Proper edge coloring
What is the minimal number K such that there exists a proper edge coloring of the complete graph on 8 vertices with K colors? A) 28 B) 8 C) 7 D) 15
asked
Jun 1
in
Graph Theory
by
Lakshman Patel RJIT
Loyal
(
8k
points)

50
views
graphtheory
edgecoloring
+2
votes
2
answers
26
Graph Theory
The largest possible number of vertices in a graph $G$, with $35$ edges and all vertices are of degree at least $3$ is $24$ $25$ $23$ $26$
asked
May 28
in
Graph Theory
by
Mr khan 3
(
127
points)

117
views
graphtheory
discretemathematics
0
votes
3
answers
27
Graph theory  Graph Theory
A simple non directed graph contains $21$ edges, $3$ vertices of degree $4$ and the other vertices are of degree $2$.Then the number of vertices in the graph is? $8$ $13$ $18$ $21$
asked
May 28
in
Study Resources
by
Mr khan 3
(
127
points)

46
views
graphtheory
discretemathematics
engineeringmathematics
+1
vote
1
answer
28
#Algorithms #DFS
Consider the tree arcs of a $DFS$ traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for computing the shortest path between every pair of vertices. the shortest path from $W$ ... in the graph. the shortest paths from $W$ to only those nodes that are leaves of $T$. the longest path in the graph.
asked
May 28
in
Algorithms
by
iarnav
Loyal
(
7.9k
points)

61
views
algorithms
graphalgorithms
graphtheory
dfs
0
votes
1
answer
29
Graph Theory DM
In this graph it is said that $a,e,b,c,b$ is a path. But according to definition in a path vertices and edges can't repeat so why this is a path. confused please clarify.
asked
May 28
in
Graph Theory
by
mbisht
(
223
points)

48
views
engineeringmathematics
discretemathematics
graphtheory
0
votes
3
answers
30
madeeasy work book
Q. State whether the following statements are FALSE. (a). if $e$ is the minimum edge weight in a connected weighted graph,it must be among the edges of at least one minimum spanning tree of the graph. (b). if $e$ is the minimum edge weight in ... weighted graph,it must be among the edges of each one minimum spanning tree of the graph. which one is correct above two option?
asked
May 24
in
Algorithms
by
abhicse
(
39
points)

84
views
graphtheory
minimumspanningtrees
Page:
1
2
3
4
5
6
...
17
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
Donation (Kerala Flood)
Schedule for GATE 2019
GATE 2019 official website
Correct way of preparation
Right process to start solving MCQs in Comp.Sc.
Follow @csegate
Gatecse
Recent questions tagged graphtheory
Recent Blog Comments
Sir I have ordered GO PDF on 16 Aug 2018 still ...
gate overflow books are awesome; every one should ...
Books are there but don't think any will leave ...
Sir i have placed the order Details are PAYMENT ...
Sir i am placing order for gate overflew book ...
38,115
questions
45,622
answers
132,334
comments
49,306
users