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 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
1
answer
1
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
2 days
ago
in
Graph Theory
by
Churchill Khangar
Active
(
2k
points)

49
views
iitkanpur
writtentest
+1
vote
1
answer
2
Narsingh Deo Problem 228
asked
4 days
ago
in
Graph Theory
by
ankitgupta.1729
Active
(
4.2k
points)

41
views
graphtheory
narsingh
deo
0
votes
1
answer
3
Show that the two graphs are isomorphic (Narsingh Deo)
asked
4 days
ago
in
Graph Theory
by
Mk Utkarsh
Boss
(
11.7k
points)

16
views
graphtheory
narsingh
deo
graphisomorphism
+1
vote
1
answer
4
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
5 days
ago
in
Graph Theory
by
Sammohan Ganguly
(
41
points)

13
views
graphtheory
discretemathematics
0
votes
0
answers
5
Number of Possible Trees
How many total Homeomorphically Irreducible Trees are possible with 'n' nodes ?
asked
Apr 11
in
Graph Theory
by
ankitgupta.1729
Active
(
4.2k
points)

17
views
graphtheory
discretemathematics
trees
0
votes
1
answer
6
#Graph Theory Any Simple way to prove this ?
asked
Apr 9
in
Graph Theory
by
iarnav
Loyal
(
6.5k
points)

50
views
graphtheory
discrete
discretemathematics
+1
vote
1
answer
7
Discrete Mathematics By Kenneth H Rosen
How to Find Whether Given Graph is NonPlanar using Kuratwoski's Theorem ?
asked
Apr 6
in
Graph Theory
by
Sayed Athar
(
93
points)

27
views
kennethrosen
discretemathematics
graphtheory
0
votes
1
answer
8
Graph Theory
Consider the following undirected graph with some edge costs missing. Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequalities NEED NOT hold? $cost(a,b)\geq 6$. $cost(b,e)\geq 5$. $cost(e,f)\geq 5$. $cost(a,d)\geq 4$. $cost(b,c)\geq 4$. Please someone solve and explain :)
asked
Apr 6
in
Graph Theory
by
gauravkc
Active
(
4.9k
points)

54
views
graphtheory
discretemathematics
graphconnectivity
+1
vote
1
answer
9
Graph Theory
Can someone solve this? Also please attempt this question on Algorithms time complexity if interested :) https://gateoverflow.in/210836/algorithmstimecomplexity
asked
Apr 5
in
Graph Theory
by
gauravkc
Active
(
4.9k
points)

50
views
graphtheory
discretemathematics
graphconnectivity
0
votes
1
answer
10
related to gate previous year
can some give example where cardinality of mincut will be < mindegree of the graph I found in question they have mentioned its <= , but i dont see any case where it is < https://gateoverflow.in/1504/gate1999_5
[closed]
asked
Apr 2
in
Graph Theory
by
mehul vaidya
Junior
(
593
points)

17
views
+1
vote
1
answer
11
UGC NET NOV 2017 PAPER 2 Q5
5. Consider the graph given below : Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are choosen is ? (1) AD, AE, AG, GC, GB, BF (2) GC, GB, BF, GA, AD, AE (3) GC, AD, GB, GA, BF, AE (4) AD, AG, GC, AE, GB, BF
asked
Mar 29
in
Graph Theory
by
kavikeve
(
459
points)

88
views
ugcnetnov2017ii
0
votes
0
answers
12
Graph Theory By Narsingh Deo
Where can I find solutions to Narsingh Deo Book for Graph theory any online links and pdf will be helpful ?
asked
Mar 26
in
Graph Theory
by
Sayed Athar
(
93
points)

44
views
0
votes
0
answers
13
Graph Theory
Walk : Vertices may repeat. Edges may repeat (Closed or Open) Trail : Vertices may repeat. Edges cannot repeat (Open) Circuit : Vertices may repeat. Edges cannot repeat (Closed) Path : Vertices cannot repeat. Edges cannot repeat (Open) Cycle : Vertices cannot repeat. Edges cannot repeat (Closed) Can someone verify these terminologies? They are pretty confusing :/
asked
Mar 26
in
Graph Theory
by
gauravkc
Active
(
4.9k
points)

45
views
graphtheory
discretemathematics
engineeringmathematics
+1
vote
1
answer
14
Graph theory
As a triangle graph is $2 $ connected, thus for a given triangle graph, $r= 2( r_1\text{ and } r_2)$ , $k=2, e = 3, v=3$, but it still doesn't satisfy the equation, Can someone tell me where did I go wrong? Thanks
asked
Mar 25
in
Graph Theory
by
Pawan Kumar 2
Active
(
4.4k
points)

84
views
graphtheory
0
votes
0
answers
15
[Graphs]IITk Written test
Graph Matching was explained. Let $S$ and $R$ be the matching graph, then a new graph $G=(SR) \cup (RS)$, will be union of vertex disjoint path and cycle. Also prove that the cycle obtained will be of even length.
asked
Mar 19
in
Graph Theory
by
rahul sharma 5
Boss
(
22.7k
points)

64
views
iitkanpur
writtentest
mtech
gate2017
+2
votes
0
answers
16
[Graphs]IITk Written test
if degree of vertices < 3, then prove that the graph will be union of vertex disjoint path and cycle
asked
Mar 19
in
Graph Theory
by
rahul sharma 5
Boss
(
22.7k
points)

58
views
iitkanpur
writtentest
interview
mtech
gate2017
0
votes
1
answer
17
GraphTheory_Problem_testpaper
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bits of strings of length $n$. We have an edge between vertex $u$ and $v$ if and only if $u$ and $v$ differ exactly in one bit position. The ratio of chromatic number of $G$ to the diameter of $G$ is . $\dfrac{1}{(2^{n1})}$ $\dfrac{1}{n}$ $\dfrac{2}{n}$ $\dfrac{3}{n}$
[closed]
asked
Mar 16
in
Graph Theory
by
RahulRoy31
(
191
points)

57
views
graphtheory
graphcoloring
0
votes
0
answers
18
UGC NET DEC 14 PAPER 2 Q  45
45. Which one of the following is used to compute cyclomatic complexity ? (A) The number of regions – 1 (B) E – N + 1, where E is the number of flow graph edges and N is the number of flow graph nodes. (C) P – 1, where P is the number of predicate nodes in the flow graph G. (D) P + 1, where P is the number of predicate nodes in the flow graph G.
[closed]
asked
Mar 8
in
Graph Theory
by
kavikeve
(
459
points)

42
views
ugcnetdec2014ii
0
votes
1
answer
19
Rosen (Graph)
Show that an edge in a simple graph is a cut edge if and only if this edge is not a part of any simple circuit in the graph.
asked
Mar 1
in
Graph Theory
by
Mk Utkarsh
Boss
(
11.7k
points)

49
views
discretemathematics
graphtheory
0
votes
1
answer
20
Rosen (Graphs)
How much storage is needed to represent a simple graph with n vertices and m edges using. a) adjacency lists? b) an adjacency matrix? c) an incidence matrix?
asked
Mar 1
in
Graph Theory
by
Mk Utkarsh
Boss
(
11.7k
points)

89
views
graphtheory
kennethrosen
+1
vote
0
answers
21
[2016]IITK interview question
1. Prove/Disprove: a) If a graph has kindependent components, it it nk+1 colorable b) converse of (a) c) If a graph is not n1 colorable, it's a clique
asked
Feb 26
in
Graph Theory
by
rahul sharma 5
Boss
(
22.7k
points)

85
views
interview
writtentest
iitkanpur
0
votes
0
answers
22
Graph theory
What is unorderd and ordered (if any) cycles in a given graph?
asked
Feb 16
in
Graph Theory
by
Sidd_
(
97
points)

46
views
+7
votes
7
answers
23
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$ is between two nodes ... mid ij \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
Boss
(
17.8k
points)

1.7k
views
gate2018
graphtheory
normal
+7
votes
5
answers
24
GATE201818
The chromatic number of the following graph is _____
asked
Feb 14
in
Graph Theory
by
gatecse
Boss
(
17.8k
points)

1.2k
views
gate2018
graphtheory
chromaticnumber
numericalanswers
0
votes
2
answers
25
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 degree 1. Prove that ... that is, 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!
Boss
(
15.1k
points)

85
views
cmi2017
graphtheory
+1
vote
1
answer
26
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!
Boss
(
15.1k
points)

59
views
graphtheory
cmi2017
0
votes
1
answer
27
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 located at intersections with ... (b) Find a spanning tree with minimum (c) Find a minimal coloring. (d) Find a minimum size vertex cover.
asked
Feb 5
in
Graph Theory
by
Tesla!
Boss
(
15.1k
points)

46
views
algorithms
graphalgorithms
cmi2017
0
votes
1
answer
28
Spanning tree
How to approach such questions ? Please provide detailed solution. Answer given is option C
asked
Feb 2
in
Graph Theory
by
kapilbk1996
(
217
points)

141
views
minimumspanningtrees
graphalgorithms
acetestseries
0
votes
1
answer
29
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
asked
Feb 1
in
Graph Theory
by
Kaluti
Loyal
(
5.3k
points)

56
views
0
votes
1
answer
30
discrete maths
What is the coefficient of x^(12) in the power series of
asked
Feb 1
in
Graph Theory
by
Kaluti
Loyal
(
5.3k
points)

98
views
Page:
1
2
3
4
5
6
...
20
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
Members at the site
reena_kandari
Neelay Upadhyaya
Mk Utkarsh
lambda
ArjuMlu
junk_mayavi
Sonu Kumar 1
Ravi kumar singh
Himanshu Sundriyal 1
gauravkc
Abhijit Sen 4
Recent Posts
barc result
Suggestion for IIITH exam
Placement Statistics for Computer Science
IIT Bombay Admission
ISRO 2018
All categories
General Aptitude
1.2k
Engineering Mathematics
4.9k
Discrete Mathematics
3.4k
Mathematical Logic
1.4k
Set Theory & Algebra
884
Combinatory
609
Graph Theory
576
Probability
621
Linear Algebra
506
Calculus
368
Digital Logic
2k
Programming & DS
3.6k
Algorithms
3k
Theory of Computation
3.9k
Compiler Design
1.5k
Operating System
2.8k
Databases
2.9k
CO & Architecture
2.5k
Computer Networks
2.9k
Non GATE
949
Others
1.3k
Admissions
408
Exam Queries
419
Tier 1 Placement Questions
17
Job Queries
55
Projects
9
Follow @csegate
Gatecse
Recent questions in Graph Theory
Recent Blog Comments
got it :) thanks man
JUST VIST "important date" under barc login
where do they mention about the time?
NOW DAYS GATE ND ITS RELATED THINGS ARE DEMANDING ...
I'm not able to edit comment on blogs
34,780
questions
41,754
answers
118,921
comments
41,399
users