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, 2019
in
Graph Theory
by
gatecse
Boss
(
17.5k
points)

40
views
cmi2019
graphconnectivity
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, 2019
in
Graph Theory
by
gatecse
Boss
(
17.5k
points)

32
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, 2019
in
Graph Theory
by
gatecse
Boss
(
17.5k
points)

43
views
cmi2018
graphtheory
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, 2019
in
Graph Theory
by
gatecse
Boss
(
17.5k
points)

26
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, 2019
in
Graph Theory
by
gmrishikumar
Active
(
2.2k
points)

91
views
graphtheory
graphalgorithms
graphconnectivity
multistagegraph
directedacyclicgraph
dag
0
votes
0
answers
6
ISI2017PCBCS1(b)
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.
asked
Apr 8, 2019
in
Graph Theory
by
akash.dinkar12
Boss
(
42.5k
points)

62
views
isi2017pcbcs
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
descriptive
+8
votes
9
answers
7
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, 2019
in
Graph Theory
by
Arjun
Veteran
(
431k
points)

4.1k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+9
votes
5
answers
8
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, 2019
in
Graph Theory
by
Arjun
Veteran
(
431k
points)

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

153
views
graphtheory
graphconnectivity
madeeasytestseries2019
madeeasytestseries
0
votes
2
answers
10
GO2019FLT134
Let $G$ be a graph of order $n$ in which every vertex has degree equal to $d$. How large must $d$ be in order to guarantee that $G$ is connected? $\frac{n}{2}$ $\lceil (n1)/2 \rceil$ $\lfloor (n+1)/2 \rfloor$ $(n1)/2$
asked
Dec 27, 2018
in
Graph Theory
by
Ruturaj Mohanty
Active
(
2.7k
points)

390
views
go2019flt1
graphtheory
graphconnectivity
+2
votes
1
answer
11
GO2019FLT154
Let $S$ be a set of $n$ elements $\{1, 2, \dots n\}$ and $G$ a graph with $2^n$ vertices, where each vertex corresponds to a distinct subset of $S$. Two vertices are adjacent if the symmetric difference of the corresponding sets has exactly $2$ elements. Every vertex in $G$ has ... $G$ and how many connected component does $G$ have, respectively? $n, 3$ $(n(n1))/2,2$ $1, n$ $n+1, n$
asked
Dec 27, 2018
in
Graph Theory
by
Ruturaj Mohanty
Active
(
2.7k
points)

217
views
go2019flt1
graphtheory
graphconnectivity
0
votes
1
answer
12
Zeal Test Series 2019: Graph Theory  Graph Connectivity
asked
Dec 22, 2018
in
Graph Theory
by
Prince Sindhiya
Loyal
(
5.9k
points)

123
views
zeal
graphtheory
graphconnectivity
zeal2019
+2
votes
1
answer
13
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
(
431k
points)

270
views
tifr2019
graphconnectivity
graphtheory
+1
vote
1
answer
14
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
(
431k
points)

385
views
tifr2019
graphconnectivity
graphtheory
difficult
+2
votes
1
answer
15
TIFR2019B15
Consider directed graphs on $n$ labelled vertices $\{1,2, \dots ,n\}$, where each vertex has exactly one edge coming in and exactly one edge going out. We allow selfloops. How many graphs have exactly two cycles ? $\sum_{k=1}^{n1} k!(nk)!$ $\frac{n!}{2}\bigg[\sum_{k=1}^{n1} \frac{1}{k(nk)}\bigg]$ $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
(
431k
points)

392
views
tifr2019
graphconnectivity
graphtheory
+3
votes
0
answers
16
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.9k
points)

140
views
zeal
graphtheory
discretemathematics
graphconnectivity
zeal2019
+2
votes
2
answers
17
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
(
883
points)

255
views
graphtheory
eulergraph
graphconnectivity
+1
vote
0
answers
18
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
(
883
points)

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

103
views
discretemathematics
graphtheory
gateforumtestseries
graphconnectivity
+1
vote
0
answers
20
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
Loyal
(
5.2k
points)

229
views
ugcnetnov2017iii
graphtheory
graphconnectivity
+4
votes
1
answer
21
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
(
205
points)

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

140
views
kennethrosen
discretemathematics
graphconnectivity
graphtheory
0
votes
1
answer
23
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.9k
points)

71
views
zeal
graphtheory
graphconnectivity
zealworkbook
0
votes
1
answer
24
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)

201
views
graphtheory
graphconnectivity
0
votes
1
answer
25
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.7k
points)

79
views
algorithms
mst
graphconnectivity
+3
votes
3
answers
26
ISRO201838
The number of edges in a regular graph of degree: $d$ and $n$ vertices is: maximum of $n$ and $d$ $n +d$ $nd$ $nd/2$
asked
Apr 22, 2018
in
Graph Theory
by
Arjun
Veteran
(
431k
points)

603
views
isro2018
graphtheory
graphconnectivity
+1
vote
1
answer
27
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)

164
views
graphtheory
discretemathematics
graphconnectivity
+1
vote
2
answers
28
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)

174
views
graphtheory
discretemathematics
graphconnectivity
0
votes
1
answer
29
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
(
36.6k
points)

159
views
graphtheory
kennethrosen
discretemathematics
graphconnectivity
+33
votes
4
answers
30
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
(
17.5k
points)

6.1k
views
gate2018
algorithms
graphalgorithms
graphconnectivity
numericalanswers
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged graphconnectivity
Recent Blog Comments
Has anyone else challenged the questions on...
@nkg_master9  For getting selected for the...
Nowhere it's mentioned.
@bond  Is it mentioned that you have to score at...
I think cutoff won't cross 85
50,737
questions
57,385
answers
198,548
comments
105,362
users