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 graphconnectivity
+1
vote
0
answers
1
Discrete mathematics and its application ,kenneth h rosen ,seventh edition,chapter 8, exercise 8.4 ques 6
asked
Aug 4
in
DS
by
saurab
(
17
points)

21
views
kennethrosen
discretemathematics
graphconnectivity
connected
component
0
votes
1
answer
2
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
0
votes
1
answer
3
SELF_DOUBT(MST)
What important point we keep in mind while finding the #(number) of spanning tree ?? from the given graph
asked
Apr 29
in
Algorithms
by
air1ankit
Active
(
3.5k
points)

47
views
algorithms
mst
graphconnectivity
0
votes
1
answer
4
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
Loyal
(
6.1k
points)

91
views
graphtheory
discretemathematics
graphconnectivity
+1
vote
2
answers
5
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
Loyal
(
6.1k
points)

95
views
graphtheory
discretemathematics
graphconnectivity
+10
votes
1
answer
6
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
(
18.1k
points)

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

61
views
datastructure
dfs
graphalgorithms
graphconnectivity
+2
votes
0
answers
8
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.6k
points)

69
views
graphtheory
graphconnectivity
engineeringmathematics
+3
votes
0
answers
9
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
(
14k
points)

117
views
graphtheory
discretemathematics
graphconnectivity
graphcoloring
0
votes
0
answers
10
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
(
825
points)

121
views
graphtheory
discretemathematics
engineeringmathematics
graphconnectivity
+1
vote
2
answers
11
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.9k
points)

150
views
graphtheory
discretemathematics
graphconnectivity
graphmatching
engineeringmathematics
+1
vote
0
answers
12
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
(
39.8k
points)

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

182
views
graphtheory
discretemathematics
graphconnectivity
+5
votes
1
answer
14
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
(
15.1k
points)

196
views
discretemathematics
graphtheory
graphconnectivity
+1
vote
0
answers
15
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.9k
points)

169
views
graphtheory
discretemathematics
graphconnectivity
graphmatching
graphcoloring
+2
votes
2
answers
16
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)

175
views
graphtheory
graphmatching
graphconnectivity
spanningtree
+1
vote
2
answers
17
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.5k
points)

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

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

323
views
graphtheory
discretemathematics
graphconnectivity
graphmatching
+2
votes
2
answers
20
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
(
24.5k
points)

218
views
graphtheory
discretemathematics
graphconnectivity
+2
votes
1
answer
21
[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
(
24.5k
points)

236
views
discretemathematics
graphtheory
graphconnectivity
+1
vote
1
answer
22
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.9k
points)

233
views
graphtheory
graphconnectivity
0
votes
0
answers
23
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
(
701
points)

177
views
graphtheory
directed
graphs
graphconnectivity
0
votes
0
answers
24
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)

119
views
graphtheory
discretemathematics
graphconnectivity
engineeringmathematics
+3
votes
3
answers
25
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
(
7.1k
points)

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

125
views
graphtheory
discretemathematics
graphconnectivity
engineeringmathematics
+1
vote
4
answers
27
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
(
7.1k
points)

322
views
graphtheory
discretemathematics
graphconnectivity
engineeringmathematics
+1
vote
2
answers
28
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
(
7.1k
points)

240
views
graphtheory
discretemathematics
graphconnectivity
engineeringmathematics
0
votes
2
answers
29
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
(
7.1k
points)

138
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
Schedule for GATE 2019
GATE 2019 official website
Correct way of preparation
Right process to start solving MCQs in Comp.Sc.
UGC NET JULY 2018 Results
Follow @csegate
Gatecse
Recent questions tagged graphconnectivity
Recent Blog Comments
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 ...
Yes, their tracking system is incomplete. ...
India post don't update the tracking details. No ...
38,084
questions
45,574
answers
132,084
comments
49,063
users