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
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
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
0
votes
1
answer
1
Graph Connectivity
Consider the given statements S1: In a simple graph G with 6 vertices, if degree of each vertex is 2, then Euler circuit exists in G. S2:In a simple graph G, if degree of each vertex is 3 then the graph G is connected. Which of the following is/are true?
asked
Nov 6
in
Graph Theory
by
dan31
(
287
points)

77
views
graphtheory
eulergraph
graphconnectivity
0
votes
0
answers
2
Graph connectivity
Let G be a connected graph with 7 connected components and each component is a tree. If G has 26 edge then number of vertices in G is?
asked
Nov 6
in
Graph Theory
by
dan31
(
287
points)

148
views
graphtheory
graphconnectivity
0
votes
2
answers
3
GATEBOOK2019DS23
A quinpartite graph is a graph whose vertices can be partitioned into five groups such that no two vertices in same group are connected via some edge. The maximum number of edges in a quinpartite graph with $10$ vertices, where cardinalities of those five sets are given as $\{2,3,2,1,2\},$ is: $16$ $20$ $26$ $39$
asked
Oct 16
in
Programming
by
GATEBOOK
Loyal
(
6.3k
points)

111
views
gb2019ds2
graphtheory
graphconnectivity
+1
vote
0
answers
4
UGCNET CS 2017
An undirected graph G (V, E) contains n (n > 2) nodes named v1 , v2 ,...,vn. Two nodes vi and vj are connected if and only if 0 < │ i − j│ ≤2. Each edge (vi , vj ) is assigned a weight i+j. The cost of the minimum spanning tree of such a graph with 10 nodes is: A) 88 B)91 C)49 D)21
asked
Sep 28
in
Graph Theory
by
aditi19
Active
(
2.1k
points)

59
views
ugcnetnov2017iii
graphtheory
graphconnectivity
+3
votes
1
answer
5
Graph theory
Stmt 1: A simple graph is necessarily connected if E > (n1)*(n2)/2. Stmt2: A simple graph with n vertices and k components has at least nk edges. Can you please explain how are these results derived?
asked
Aug 26
in
Mathematical Logic
by
Nidhi Budhraja
(
203
points)

114
views
graphtheory
discretemathematics
graphconnectivity
+1
vote
1
answer
6
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)

81
views
kennethrosen
discretemathematics
graphconnectivity
connected
component
0
votes
1
answer
7
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
(
159
points)

125
views
graphtheory
graphconnectivity
0
votes
1
answer
8
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
(
4.1k
points)

54
views
algorithms
mst
graphconnectivity
0
votes
1
answer
9
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.9k
points)

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

121
views
graphtheory
discretemathematics
graphconnectivity
+13
votes
1
answer
11
GATE201843
Let $G$ be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1, 2,.., 100. There is an edge between vertices $u$ and $v$ if and only if the label of $u$ ... $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.3k
points)

2.8k
views
gate2018
algorithms
graphalgorithms
graphconnectivity
numericalanswers
+2
votes
0
answers
12
DFS depth first search
asked
Jan 25
in
DS
by
budhu
(
159
points)

86
views
datastructure
dfs
graphalgorithms
graphconnectivity
+2
votes
0
answers
13
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)

78
views
graphtheory
graphconnectivity
engineeringmathematics
+5
votes
0
answers
14
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
(
29.7k
points)

163
views
graphtheory
discretemathematics
graphconnectivity
graphcoloring
0
votes
0
answers
15
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
(
975
points)

139
views
graphtheory
discretemathematics
engineeringmathematics
graphconnectivity
+1
vote
2
answers
16
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
(
5k
points)

174
views
graphtheory
discretemathematics
graphconnectivity
graphmatching
engineeringmathematics
+1
vote
0
answers
17
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
(
41.5k
points)

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

210
views
graphtheory
discretemathematics
graphconnectivity
+6
votes
1
answer
19
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
(
17k
points)

210
views
discretemathematics
graphtheory
graphconnectivity
+1
vote
0
answers
20
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
(
5k
points)

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

197
views
graphtheory
graphmatching
graphconnectivity
spanningtree
+1
vote
2
answers
22
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
(
6k
points)

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

107
views
graphtheory
graphconnectivity
+3
votes
3
answers
24
[Discrete Maths] Graph Theory Rosen,Chromatic number
asked
Jun 13, 2017
in
Mathematical Logic
by
rahul sharma 5
Boss
(
25.9k
points)

355
views
graphtheory
discretemathematics
graphconnectivity
graphmatching
+2
votes
2
answers
25
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
(
25.9k
points)

236
views
graphtheory
discretemathematics
graphconnectivity
+3
votes
1
answer
26
[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
(
25.9k
points)

247
views
discretemathematics
graphtheory
graphconnectivity
Page:
1
2
3
4
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
IIT HYDERABAD M.Tech (RA) 3Years Winter Session Interview experience
INDIAN AIR FORCE
GATE BOOK _ TEST SERIES DOUBT_
Visualizing complex C code
GATE Book Test Series
Follow @csegate
Gatecse
Recent questions tagged graphconnectivity
Recent Blog Comments
First of all, congratulations!
I can...
Congrats man. You wrote gate in B.Tech 3rd year?
Thank You so much sir for giving tips. I will...
Please elucidate this really important...
44,312
questions
49,803
answers
164,516
comments
65,865
users