The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook 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
Recent questions tagged graphconnectivity
0
votes
1
answer
1
CMI2019B4
Consider the assertion: Any connected undirected graph $G$ with at least two vertices contains a vertex $v$ such that deleting $v$ from $G$ results in a connected graph. Either give a proof of the assertion, or give a counterexample (thereby disproving the assertion).
asked
Sep 13
in
Graph Theory
by
gatecse
Boss
(
16.6k
points)

15
views
cmi2019
graphconnectivity
undirectedgraph
0
votes
1
answer
2
CMI2018A9
Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multitalented ... : Find a maximum length simple cycle Find a maximum size independent set Find a maximum matching Find a maximal connected component
asked
Sep 13
in
Graph Theory
by
gatecse
Boss
(
16.6k
points)

15
views
cmi2018
graphtheory
graphconnectivity
graphmatching
independentset
descriptive
+1
vote
1
answer
3
CMI2018B3
Let $G$ be a simple graph on $n$ vertices. Prove that if $G$ has more than $\binom{n1}{2}$ edges then $G$ is connected. For every $n>2$, find a graph $G_{n}$ which has exactly $n$ vertices and $\binom{n1}{2}$ edges, and is not connected.
asked
Sep 13
in
Graph Theory
by
gatecse
Boss
(
16.6k
points)

20
views
cmi2018
graphtheory
simplegraph
graphconnectivity
descriptive
+1
vote
0
answers
4
CMI2018B5
Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given to you by a $01$ matrix $A$ of size $n\times n$ as follows. For any $1\leq i,j\leq n,$ the entry $A[i,j]=1$ if and only if ... any two vertices are connected to each other by paths. Give a simple algorithm to find the number of connected components in $G.$ Analyze the time taken by your procedure.
asked
Sep 13
in
Graph Theory
by
gatecse
Boss
(
16.6k
points)

14
views
cmi2018
graphtheory
undirectedgraph
graphconnectivity
connectedcomponents
descriptive
+1
vote
1
answer
5
Difference between DAG and Multistage graph
I have trouble understanding the difference between DAG and Multistage graph. I know what each of them is But I think that a multistage graph is also a DAG. Are multistage graphs a special kind of DAG?
asked
Apr 28
in
Graph Theory
by
gmrishikumar
Active
(
2k
points)

72
views
graphtheory
graphalgorithms
graphconnectivity
multistagegraph
directedacyclicgraph
dag
+5
votes
8
answers
6
GATE201912
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to $n!$ $(n1)!$ $1$ $\frac{(n1)!}{2}$
asked
Feb 7
in
Graph Theory
by
Arjun
Veteran
(
423k
points)

3.3k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+4
votes
3
answers
7
GATE201938
Let $G$ be any connected, weighted, undirected graph. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimumweight edge crossing the cut. Which of the following statements is/are TRUE? I only II only Both I and II Neither I nor II
asked
Feb 7
in
Graph Theory
by
Arjun
Veteran
(
423k
points)

2.9k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+1
vote
1
answer
8
MadeEasy Full Length Test 2019: Graph Theory  Vertex Connectivity
The Vertex Connectivity of Graph is : 1 2 3 None
asked
Jan 16
in
Graph Theory
by
Na462
Loyal
(
6.8k
points)

132
views
graphtheory
graphconnectivity
madeeasytestseries2019
madeeasytestseries
0
votes
1
answer
9
Zeal Test Series 2019: Graph Theory  Graph Connectivity
asked
Dec 22, 2018
in
Graph Theory
by
Prince Sindhiya
Loyal
(
5.6k
points)

112
views
zeal
graphtheory
graphconnectivity
zeal2019
0
votes
1
answer
10
TIFR2019B3
A graph is $d$ – regular if every vertex has degree $d$. For a $d$ – regular graph on $n$ vertices, which of the following must be TRUE? $d$ divides $n$ Both $d$ and $n$ are even Both $d$ and $n$ are odd At least one of $d$ and $n$ is odd At least one of $d$ and $n$ is even
asked
Dec 18, 2018
in
Graph Theory
by
Arjun
Veteran
(
423k
points)

198
views
tifr2019
graphconnectivity
graphtheory
+1
vote
1
answer
11
TIFR2019B12
Let $G=(V,E)$ be a directed graph with $n(\geq 2)$ vertices, including a special vertex $r$. Each edge $e \in E$ has a strictly positive edge weight $w(e)$. An arborescence in $G$ rooted at $r$ is a subgraph $H$ of $G$ in which every ... $w^*$ is less than the weight of the minimum weight directed Hamiltonian cycle in $G$, when $G$ has a directed Hamiltonian cycle
asked
Dec 18, 2018
in
Graph Theory
by
Arjun
Veteran
(
423k
points)

314
views
tifr2019
graphconnectivity
graphtheory
difficult
+1
vote
1
answer
12
TIFR2019B15
Consider directed graphs on $n$ labelled vertices $\{1,2, \dots ,n\}$, where each vertex has exactly one edge coming in and exactly coming in and exactly one edge going out. We allow selfloops. How many graphs have exactly two cycles ? $\sum_{k=1}^{n1} k!(nk)!$ ... $n!\bigg[\sum_{k=1}^{n1} \frac{1}{k}\bigg]$ $\frac{n!(n1)}{2}$ None of the above
asked
Dec 18, 2018
in
Graph Theory
by
Arjun
Veteran
(
423k
points)

306
views
tifr2019
graphconnectivity
graphtheory
+3
votes
0
answers
13
Zeal Test Series 2019: Graph Theory  Graph Connectivity
i didn't read the concept related to strongly connected components please it describe it for this question
asked
Nov 11, 2018
in
Graph Theory
by
Prince Sindhiya
Loyal
(
5.6k
points)

126
views
zeal
graphtheory
discretemathematics
graphconnectivity
zeal2019
+1
vote
2
answers
14
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, 2018
in
Graph Theory
by
dan31
Junior
(
877
points)

226
views
graphtheory
eulergraph
graphconnectivity
+1
vote
0
answers
15
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, 2018
in
Graph Theory
by
dan31
Junior
(
877
points)

219
views
graphtheory
graphconnectivity
0
votes
0
answers
16
Gateforum Test Series: Graph Theory  Graph connectivity
asked
Oct 29, 2018
in
Graph Theory
by
Gupta731
Active
(
4.7k
points)

93
views
discretemathematics
graphtheory
gateforumtestseries
graphconnectivity
+1
vote
0
answers
17
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, 2018
in
Graph Theory
by
aditi19
Active
(
5k
points)

208
views
ugcnetnov2017iii
graphtheory
graphconnectivity
+4
votes
1
answer
18
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, 2018
in
Mathematical Logic
by
Nidhi Budhraja
(
197
points)

201
views
graphtheory
discretemathematics
graphconnectivity
+1
vote
1
answer
19
Kenneth Rosen Edition 6th Exercise 8.4 Question 6 (Page No. 574)
how many connected components does the following graph has ?find its connected component ?
asked
Aug 4, 2018
in
Graph Theory
by
saurab
(
21
points)

131
views
kennethrosen
discretemathematics
graphconnectivity
graphtheory
0
votes
1
answer
20
Zeal Workbook: Graph Theory  Graph Connectivity
Prove that every graph with n vertices and k components has atleast nk edges.
asked
Jul 29, 2018
in
Graph Theory
by
Prince Sindhiya
Loyal
(
5.6k
points)

63
views
zeal
graphtheory
graphconnectivity
zealworkbook
0
votes
1
answer
21
ACE Bits and bYtes
Minimum no of edges necessary in a simple graph with 10 vertices to ensure connectivity is_______.
asked
Jul 24, 2018
in
Graph Theory
by
abhishek1995_cse
(
111
points)

191
views
graphtheory
graphconnectivity
0
votes
1
answer
22
SELF_DOUBT(MST)
What important point we keep in mind while finding the #(number) of spanning tree ?? from the given graph
asked
Apr 29, 2018
in
Algorithms
by
air1ankit
Active
(
4.4k
points)

69
views
algorithms
mst
graphconnectivity
+1
vote
1
answer
23
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, 2018
in
Graph Theory
by
gauravkc
Loyal
(
7.8k
points)

157
views
graphtheory
discretemathematics
graphconnectivity
+1
vote
2
answers
24
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, 2018
in
Graph Theory
by
gauravkc
Loyal
(
7.8k
points)

162
views
graphtheory
discretemathematics
graphconnectivity
0
votes
1
answer
25
Kenneth Rosen Edition 6th Exercise 8.4 Question 70 (Page No. 565 )
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, 2018
in
Graph Theory
by
Mk Utkarsh
Boss
(
35.4k
points)

150
views
graphtheory
kennethrosen
discretemathematics
graphconnectivity
+30
votes
3
answers
26
GATE201843
Let $G$ be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 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 label ... $G$, and $z$ denote the number of connected components in $G$. Then, $y+10z$ = ____
asked
Feb 14, 2018
in
Algorithms
by
gatecse
Boss
(
16.6k
points)

5.2k
views
gate2018
algorithms
graphalgorithms
graphconnectivity
numericalanswers
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 ... number of edges. Find a spanning tree with minimum cost. Find a minimal coloring. Find a minimum size vertex cover.
asked
Feb 5, 2018
in
Graph Theory
by
Tesla!
Boss
(
18.2k
points)

106
views
cmi2017
graphconnectivity
easy
+2
votes
0
answers
28
DFS depth first search
asked
Jan 25, 2018
in
DS
by
budhu
(
139
points)

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

85
views
graphtheory
graphconnectivity
engineeringmathematics
+6
votes
0
answers
30
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, 2018
in
Graph Theory
by
Mk Utkarsh
Boss
(
35.4k
points)

247
views
graphtheory
discretemathematics
graphconnectivity
graphcoloring
Page:
1
2
3
4
5
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
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Minimal Deterministic Finite Automata
To be aware of fake GATE test series
Follow @csegate
Recent questions tagged graphconnectivity
Recent Blog Comments
still it's usefull for practice purpose and...
@Satbir Its a valuable info..Thanks
It is the 2019 question paper given as a mock...
Favorite is not working for blogs.. In favorites...
Favourite option does work. But list options...
50,650
questions
56,185
answers
193,938
comments
94,689
users