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 graphconnectivity
0
votes
1
answer
1
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
2
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
+7
votes
1
answer
3
GATE201843
Let $G$ be a graph with 100! vertices!, with each vertex labelled by a distinct permutation od the numbers 1, 2, ..., 100. There is an edge between vertices $u$ and $v$ if and only if the label of $u$ can be obtained by swapping two adjacent numbers in the ... $v$. Let $y$ denote the degree of a vertex in $G$, and $z$ denote the number of connected components in $G$. Then $y+10z$ = ____
asked
Feb 14
in
Algorithms
by
gatecse
Boss
(
17.8k
points)

1.5k
views
gate2018
algorithms
graphalgorithms
graphconnectivity
numericalanswers
+1
vote
0
answers
4
DFS depth first search
asked
Jan 25
in
DS
by
budhu
(
139
points)

44
views
datastructure
dfs
graphalgorithms
graphconnectivity
+2
votes
0
answers
5
graph
Is there any algorithm to find number of different minimum spanning trees for a graph?
asked
Jan 18
in
Mathematical Logic
by
raviyogi
Active
(
2.5k
points)

62
views
graphtheory
graphconnectivity
engineeringmathematics
+3
votes
0
answers
6
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
(
11.7k
points)

86
views
graphtheory
discretemathematics
graphconnectivity
graphcoloring
0
votes
0
answers
7
Graph Theory Doubt
Let G be a planar graph with 7 vertices, 10 edges and 3 components then the number of regions are : a)24 b)37 c)7 d)10 Answer given : 7 How to solve this ? Is there any formulae for number of regions calculation? The only one I know is r=en+2 for any planar graph.
asked
Dec 25, 2017
in
Graph Theory
by
Sourajit25
Junior
(
587
points)

92
views
graphtheory
discretemathematics
engineeringmathematics
graphconnectivity
+1
vote
2
answers
8
graph theory
Maximum no of edges in a trianglefree, simple planar graph with 10 vertices
asked
Dec 23, 2017
in
Graph Theory
by
Parshu gate
Active
(
4.8k
points)

119
views
graphtheory
discretemathematics
graphconnectivity
graphmatching
engineeringmathematics
+1
vote
0
answers
9
Maths: Graph Theory
Let G be a 3regular graph and S be a minimum vertex cut of G with S = 5 The the size of smallest edge cut of G is _______ (A)4 (B) 5 (C) 6 (D) None of the above
asked
Dec 3, 2017
in
Graph Theory
by
Manu Thakur
Boss
(
39k
points)

142
views
graphtheory
discretemathematics
graphconnectivity
+6
votes
1
answer
10
Discrete maths: Graph theory [Test series]
asked
Nov 15, 2017
in
Graph Theory
by
rahul sharma 5
Boss
(
22.7k
points)

167
views
graphtheory
discretemathematics
graphconnectivity
+5
votes
1
answer
11
Graph Theory
Graph G(V,E) is a connected planar graph with no cycle of length less than 4 edges, if V = 15 then maximum value of E is: The answer given is 26.
asked
Nov 13, 2017
in
Graph Theory
by
Shubhanshu
Boss
(
14.9k
points)

176
views
discretemathematics
graphtheory
graphconnectivity
+1
vote
0
answers
12
chromatic number
Let G be a planar Graph Such that every phase is bordered by exactly 3 edges which of the following can never be value for X(G) a)2 b)3 C)4 d)none of these
asked
Nov 11, 2017
in
Graph Theory
by
Parshu gate
Active
(
4.8k
points)

130
views
graphtheory
discretemathematics
graphconnectivity
graphmatching
chromaticnumber
+2
votes
2
answers
13
Graph Theory
Consider a 'reversed Kruskal' Algorithm for computing a MST. Initialize T to be the set of all edges in the graph. Now consider edges from largest to smallest cost. For each edge, delete it from T if that edge belongs to a cycle in T. Assuming all the edge costs are distinct, does this new algorithm correctly compute a MST? a) Yes b) no c) cant say
asked
Sep 14, 2017
in
Graph Theory
by
Rakshit Gupta
(
33
points)

156
views
graphtheory
graphmatching
graphconnectivity
spanningtree
+1
vote
1
answer
14
Graph Theory Question
Consider a social network with n persons. Two persons A and B are said to be connected if either they are friends or they are related through a sequence of friends: that is, there exists a set of persons F1, . . . , Fm such that A and F1 ... . It is known that there are k persons such that no pair among them is connected. What is the maximum number of friendships possible?
asked
Sep 9, 2017
in
Graph Theory
by
Kaluti
Loyal
(
5.3k
points)

158
views
graphconnectivity
+1
vote
0
answers
15
graph theory
can we say a null graph is eulerian circuit and hamiltonian circuit?
asked
Jul 8, 2017
in
Mathematical Logic
by
akankshadewangan24
Active
(
3.9k
points)

90
views
graphtheory
graphconnectivity
+1
vote
3
answers
16
[Discrete Maths] Graph Theory Rosen,Chromatic number
asked
Jun 13, 2017
in
Mathematical Logic
by
rahul sharma 5
Boss
(
22.7k
points)

279
views
graphtheory
discretemathematics
graphconnectivity
graphmatching
+2
votes
2
answers
17
Discrete Maths Graph theory
What are the necessary and sufficient conditions for Euler path and Circuit in directed graph?
asked
Jun 13, 2017
in
Mathematical Logic
by
rahul sharma 5
Boss
(
22.7k
points)

179
views
graphtheory
discretemathematics
graphconnectivity
+2
votes
1
answer
18
[Discrete Maths] Graph theory
What is the vertex connectivity and edge connectivity of complete graph? Is it n or n1?
asked
Jun 7, 2017
in
Graph Theory
by
rahul sharma 5
Boss
(
22.7k
points)

210
views
discretemathematics
graphtheory
graphconnectivity
+1
vote
1
answer
19
2  connected graph
For a regular graph how much large the value of degree (for each vertices) should be such that the graph is $2$  connected. (vertex wise). I did in this way : $\begin{align*} &\quad \kappa(G) \leq \frac{2\cdot e}{n} \qquad \text{ where } \ ... is 3 regular and not 2 connected although $d \geq 2$ is satisfied. Why this $d \geq 2$ is trivial and not working in some cases ?
asked
May 19, 2017
in
Graph Theory
by
Debashish Deka
Veteran
(
56.2k
points)

222
views
graphtheory
graphconnectivity
0
votes
0
answers
20
GATE Graph Theory
Let G = (V, E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G? ( A ) G1 = (V, E1) where E1 = {(u, v)  (u, v) ∉ E} ( B ) G2 ... D ) G4 = (V4, E) where V4 is the set of vertices in G which are not isolated Can anyone give a detailed answer to this question, please? :)
asked
May 12, 2017
in
Graph Theory
by
Bongbirdie
Junior
(
667
points)

161
views
graphtheory
directed
graphs
graphconnectivity
0
votes
0
answers
21
Graph Theory
algorithm to find more than one path between any two vertices of a graph G=(V,E) , with a complexity of O(VE) ?
asked
May 12, 2017
in
Graph Theory
by
Pavan Kumar Munnam
Boss
(
10.9k
points)

114
views
graphtheory
discretemathematics
graphconnectivity
engineeringmathematics
+3
votes
3
answers
22
graph theory
A graph consists of only one vertex,which is isolated ..Is that graph A) a complete graph ??? B) a clique??? C) connected graph ??? Please explain your answer ...
asked
Apr 7, 2017
in
Graph Theory
by
Vicky rix
Loyal
(
6.7k
points)

253
views
graphtheory
discretemathematics
graphconnectivity
engineeringmathematics
0
votes
1
answer
23
graph theory
asked
Mar 12, 2017
in
Graph Theory
by
Vicky rix
Loyal
(
6.7k
points)

115
views
graphtheory
discretemathematics
graphconnectivity
engineeringmathematics
+1
vote
4
answers
24
graph theory
chromatic number of a graph <= ( maxdegree of the graph ) + 1 can somebody explain how ?
asked
Mar 11, 2017
in
Graph Theory
by
Vicky rix
Loyal
(
6.7k
points)

264
views
graphtheory
discretemathematics
graphconnectivity
engineeringmathematics
+1
vote
2
answers
25
graph theory
A graph with n vertices and 0 edges.can this graph be called as Bipartite ? i mean can we simply partition the n vertices into two sets of vertices such that there is no edge within the set as well there is no edge between the two sets and say it as a Bipartite graph ?
asked
Mar 11, 2017
in
Graph Theory
by
Vicky rix
Loyal
(
6.7k
points)

230
views
graphtheory
discretemathematics
graphconnectivity
engineeringmathematics
0
votes
2
answers
26
graph theory
State TRUE or FALSE. The chromatic number of a Bipartite graph is ALWAYS 2.
asked
Mar 11, 2017
in
Graph Theory
by
Vicky rix
Loyal
(
6.7k
points)

133
views
graphtheory
discretemathematics
graphconnectivity
engineeringmathematics
0
votes
1
answer
27
graph theory
The cardinality of the vertexcut ( seperating set ) of a complete graph with n vertices is ___
asked
Mar 11, 2017
in
Graph Theory
by
Vicky rix
Loyal
(
6.7k
points)

182
views
graphtheory
discretemathematics
graphconnectivity
engineeringmathematics
0
votes
1
answer
28
graph theory
In a Bipartite graph,the size of the maximum matching is equal to the size of the minimum vertex cover ...can somebody prove this logically ?
asked
Mar 10, 2017
in
Graph Theory
by
Vicky rix
Loyal
(
6.7k
points)

127
views
graphtheory
discretemathematics
graphconnectivity
engineeringmathematics
+1
vote
2
answers
29
graph theory
The number of independent sets in a complete graph with n vertices is ____
asked
Mar 10, 2017
in
Graph Theory
by
Vicky rix
Loyal
(
6.7k
points)

133
views
graphtheory
discretemathematics
graphconnectivity
engineeringmathematics
Page:
1
2
3
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
barc result
Suggestion for IIITH exam
Placement Statistics for Computer Science
IIT Bombay Admission
ISRO 2018
Follow @csegate
Gatecse
Recent questions tagged graphconnectivity
Recent Blog Comments
...
link? not getting it
Declared!
got it :) thanks man
JUST VIST "important date" under barc login
34,782
questions
41,758
answers
118,940
comments
41,401
users