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 in Graph Theory
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
Web Page
Connectivity,
Matching,
Coloring.
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
0
votes
0
answers
1
Kenneth rosen
How many nonisomorphic directed graphs are there with $n$ vertices when $n$ is $2$ $3$ $4$
asked
3 days
ago
in
Graph Theory
by
swati96
(
37
points)

14
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
3 days
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
3 days
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?
[closed]
asked
3 days
ago
in
Graph Theory
by
swati96
(
37
points)

5
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
3 days
ago
in
Graph Theory
by
piya
(
91
points)

16
views
engineeringmathematics
discretemathematics
graphtheory
0
votes
1
answer
6
Perfect Matching
Perfect matching is a set of edges such that each vertex appears only once and all vertices appear at least once (EXACTLY one appearance). So for n vertices perfect matching will have n/2 edges and there won't be any perfect matching if n is odd. ... 't know whether i got it properly or not. Can please anybody explain the Perfect matching in a complete graph with simpler examples ?
asked
Jun 10
in
Graph Theory
by
Na462
Active
(
3.3k
points)

21
views
graphmatching
0
votes
1
answer
7
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.1k
points)

44
views
algorithms
graphtheory
djikstra
0
votes
0
answers
8
[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.8k
points)

23
views
graphtheory
narsinghdeo
0
votes
0
answers
9
[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.8k
points)

13
views
graphtheory
narsinghdeo
0
votes
2
answers
10
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.
[closed]
asked
Jun 7
in
Graph Theory
by
Ayush Upadhyaya
Loyal
(
8.8k
points)

65
views
graphtheory
graphcoloring
0
votes
0
answers
11
Number of distinct cycles of length 4 in a complete graph of 6 labelled vertices.
[closed]
asked
Jun 6
in
Graph Theory
by
Ayush Upadhyaya
Loyal
(
8.8k
points)

50
views
graphtheory
engineeringmathematics
0
votes
2
answers
12
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.8k
points)

38
views
engineeringmathematics
graphtheory
0
votes
2
answers
13
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.8k
points)

61
views
graphtheory
deo
narsingh
0
votes
0
answers
14
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.
[closed]
asked
Jun 2
in
Graph Theory
by
Ayush Upadhyaya
Loyal
(
8.8k
points)

37
views
graphtheory
narsingh
deo
0
votes
0
answers
15
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
0
votes
0
answers
16
Keneth
Are there any graph having chromatic number 1 ??????
asked
Jun 1
in
Graph Theory
by
vijju532
(
61
points)

94
views
discretemathematics
kennethrosen
+2
votes
2
answers
17
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)

101
views
graphtheory
discretemathematics
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)

36
views
engineeringmathematics
discretemathematics
graphtheory
+1
vote
2
answers
19
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
20
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
21
TIFR 2018
[closed]
asked
May 5
in
Graph Theory
by
jatinkumar
(
203
points)

33
views
usertifr2018
usermod
graphtheory
numericalability
0
votes
1
answer
22
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
23
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
1
answer
24
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
+1
vote
1
answer
25
PGEE 2018
Consider Undirected Graph G having vertex V {A,B,C,D,E} and edge pair as E {AB BD BE AC CE CD} A) Given graph is disconnected B) Given graph is complete C) Given graph has vertex connectivity 2 D) Given graph has edge connectivity 1
asked
Apr 21
in
Graph Theory
by
Tesla!
Boss
(
16.1k
points)

69
views
iiithpgee
graphtheory
0
votes
2
answers
26
PGEE 2018
Maximal Independence Number is the cardinality of maximal independence set ( Independence set V of graph G is set in which no vertex of the set have a direct edge between them). 1) Maximal Independence Number of a complete graph is n1 2) Maximal Independence ... Maximal Independence Number of a complete graph is 1 4) Maximal Independence Number of complete graph is $\geq \frac{n}{2}$
asked
Apr 21
in
Graph Theory
by
Tesla!
Boss
(
16.1k
points)

69
views
graphtheory
iiithpgee
0
votes
1
answer
27
IIT Kanpur Sample Test Paper
Given an undirected graph with vertices as your friends and edges between people who do not talk to each other. Your task is to invite as many guests to your party such that there are no two friends at the party who have problem talking to each ... instance of: A. Maximum vertex cover. B. Maximum cut. C. Maximum eigenvalue of adjacency matrix. D. None of the above.
asked
Apr 17
in
Graph Theory
by
Churchill Khangar
Active
(
2.1k
points)

152
views
iitkanpur
writtentest
+1
vote
1
answer
28
Narsingh Deo Problem 228
asked
Apr 16
in
Graph Theory
by
ankitgupta.1729
Loyal
(
6k
points)

76
views
graphtheory
narsingh
deo
0
votes
2
answers
29
Show that the two graphs are isomorphic (Narsingh Deo)
asked
Apr 15
in
Graph Theory
by
Mk Utkarsh
Boss
(
12.6k
points)

52
views
graphtheory
narsingh
deo
graphisomorphism
+1
vote
1
answer
30
Graph Theory
Let G be a simple graph in which every vertex has degree 3. Prove that G decomposes into claws iff G is bipartite.
asked
Apr 15
in
Graph Theory
by
Sammohan Ganguly
(
417
points)

29
views
graphtheory
discretemathematics
Page:
1
2
3
4
5
6
...
21
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
UGC NET 2018 Admit Card available for Download
IIIT Hyderabad Interview Experience
The GATE journey
BARC Interview Experience 15th June 2018
COAP Admission and IITD, IITK Interview Experience 2018
All categories
General Aptitude
1.3k
Engineering Mathematics
5.2k
Discrete Mathematics
3.6k
Mathematical Logic
1.4k
Set Theory & Algebra
922
Combinatory
637
Graph Theory
602
Probability
651
Linear Algebra
527
Calculus
388
Digital Logic
2k
Programming & DS
3.7k
Algorithms
3.2k
Theory of Computation
4k
Compiler Design
1.6k
Operating System
2.8k
Databases
3k
CO & Architecture
2.6k
Computer Networks
3k
Non GATE
1k
Others
1.3k
Admissions
486
Exam Queries
434
Tier 1 Placement Questions
17
Job Queries
56
Projects
9
Follow @csegate
Gatecse
Recent questions in Graph Theory
Recent Blog Comments
Congrats.
Congratulations Priyendu, thanks for sharing the ...
Most probably IITK. Analyzed a lot and finally ...
Congratulations! Which college are you aiming for ...
yes. I'm joining bits goa. I'm from goa also so ...
36,136
questions
43,587
answers
123,889
comments
42,832
users