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
0
answers
1
Kenneth rosen
How many nonisomorphic directed graphs are there with $n$ vertices when $n$ is $2$ $3$ $4$
asked
1 day
ago
in
Graph Theory
by
swati96
(
37
points)

12
views
engineeringmathematics
discretemathematics
kennethrosen
graphtheory
0
votes
0
answers
2
Kenneth rosen
How many nonisomorphic graphs are there with six vertices and four edges?
asked
1 day
ago
in
Graph Theory
by
swati96
(
37
points)

5
views
engineeringmathematics
discretemathematics
graphtheory
0
votes
0
answers
3
Graphs, kenneth rosen
How many nonisomorphic simple graphs are there with five vertices and three edges?
asked
1 day
ago
in
Graph Theory
by
swati96
(
37
points)

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

4
views
engineeringmathematics
discretemathematics
graphtheory
0
votes
1
answer
5
spanning tree
How we get maximum no. of spanning tree for give $n$ node is $n^{(n2)}$
asked
1 day
ago
in
Graph Theory
by
piya
(
73
points)

14
views
engineeringmathematics
discretemathematics
graphtheory
0
votes
1
answer
6
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
(
1k
points)

43
views
algorithms
graphtheory
djikstra
0
votes
0
answers
7
[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
Loyal
(
8.7k
points)

22
views
graphtheory
narsinghdeo
0
votes
0
answers
8
[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
Loyal
(
8.7k
points)

11
views
graphtheory
narsinghdeo
0
votes
2
answers
9
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
Loyal
(
8.7k
points)

63
views
graphtheory
graphcoloring
0
votes
0
answers
10
Number of distinct cycles of length 4 in a complete graph of 6 labelled vertices.
asked
Jun 6
in
Graph Theory
by
Ayush Upadhyaya
Loyal
(
8.7k
points)

50
views
graphtheory
engineeringmathematics
0
votes
2
answers
11
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
Loyal
(
8.7k
points)

38
views
engineeringmathematics
graphtheory
0
votes
2
answers
12
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
Loyal
(
8.7k
points)

60
views
graphtheory
deo
narsingh
0
votes
0
answers
13
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
Loyal
(
8.7k
points)

36
views
graphtheory
narsingh
deo
0
votes
0
answers
14
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
(
7.7k
points)

50
views
graphtheory
edgecoloring
+2
votes
2
answers
15
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
(
121
points)

100
views
graphtheory
discretemathematics
0
votes
3
answers
16
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
(
121
points)

41
views
graphtheory
discretemathematics
engineeringmathematics
0
votes
1
answer
17
#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.2k
points)

38
views
algorithms
graphalgorithms
graphtheory
dfs
0
votes
1
answer
18
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
(
161
points)

35
views
engineeringmathematics
discretemathematics
graphtheory
0
votes
3
answers
19
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)

77
views
graphtheory
minimumspanningtrees
+1
vote
2
answers
20
Graph Theory #self doubt
Can both euler path and euler circuit exist in same graph. Can both Hamiltonian path and Hamiltonian circuit exist in same graph.
asked
May 24
in
Graph Theory
by
Abhinavg
(
259
points)

72
views
graphtheory
0
votes
1
answer
21
Clique with one vertex
Is there a clique possible in Graph with one vertex? I mean, is a singleton vertex in itself is a complete subgraph and can be called a clique.
asked
May 18
in
Graph Theory
by
iarnav
Loyal
(
7.2k
points)

96
views
graphtheory
engineeringmathematics
0
votes
0
answers
22
#Algorithms #DFS How to find if a directed graph G is strongly connected using DFS in one pass?
asked
May 13
in
Algorithms
by
iarnav
Loyal
(
7.2k
points)

27
views
graphtheory
algorithms
dfs
graphalgorithms
0
votes
0
answers
23
TIFR 2018
asked
May 5
in
Graph Theory
by
jatinkumar
(
203
points)

33
views
usertifr2018
usermod
graphtheory
numericalability
0
votes
1
answer
24
Graph Theory & Permutations
Given 3 connected components with 2,2,3 vertices. In how many ways can we add two edges to connect the whole graph? Also, if possible generalise the method for graph with k connected components each having ni vertices. Ans=84
asked
May 4
in
Graph Theory
by
Hakuna Matata
(
317
points)

74
views
graphtheory
discretemathematics
permutationsandcombinations
+1
vote
2
answers
25
IISc CDS (MTechR)
Number of distinct simple graphs possible, given 8 vertices and not considering self loops?
asked
May 3
in
Graph Theory
by
Hakuna Matata
(
317
points)

89
views
iisc
cds
mtechr
graphtheory
writtentest
0
votes
2
answers
26
Connected Components
My Doubt is : 1. If n vertices are there and p are the connected components then total np edges will be there. 2. In a simple graph with n vertices and p connected components there are atmost (np)(np+1)/2 number of edges Now which to ... the answer. Solution of made easy: (Please tell how did they approached the question and which way is the best way to do such questions)
asked
May 2
in
Algorithms
by
Na462
Active
(
3.3k
points)

154
views
discretemathematics
graphtheory
0
votes
1
answer
27
Spanning trees
Suppose that a graph G has a minimum spanning tree already computed. How quickly can we update the minimum spanning tree if we add a new vertex and incident edges to G?
asked
Apr 29
in
Algorithms
by
Durgesh Singh
Junior
(
877
points)

42
views
algorithms
graphtheory
minimumspanningtrees
0
votes
1
answer
28
Self Doubt
How can we distinguish b/w back edge, the forward edge and cross edge in BFS or DFS traversal in Graphs?
asked
Apr 29
in
Algorithms
by
Durgesh Singh
Junior
(
877
points)

42
views
algorithms
graphtheory
0
votes
1
answer
29
Induction
Prove that the number of edges in a graph with exactly one triangle is at most \begin{align*} \frac{\left( n  1 \right )^2}{4} + 2 \end{align*}
asked
Apr 27
in
Graph Theory
by
Debashish Deka
Veteran
(
56.6k
points)

50
views
induction
graphtheory
combinatoricsiitb
0
votes
1
answer
30
Regular polyhedra
Is regular polyhedra in graph theory in our Gate syllabus 2019?
asked
Apr 25
in
Mathematical Logic
by
Na462
Active
(
3.3k
points)

24
views
graphtheory
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
The GATE journey
BARC Interview Experience 15th June 2018
COAP Admission and IITD, IITK Interview Experience 2018
MS Interview Experience at IITK
Effect of Academic/ Career Gap during Mtech Placements at IIT/NIT
Follow @csegate
Gatecse
Recent questions tagged graphtheory
Recent Blog Comments
Prepare for interviews from the date of GATE ...
@ krishn.jh I started my first revision in ...
Congrates @
Inspiring!!!
Thank you :)
36,088
questions
43,531
answers
123,704
comments
42,762
users