Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged graph-connectivity
0
votes
2
answers
61
CMI2019-B-4
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).
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....
gatecse
727
views
gatecse
asked
Sep 13, 2019
Graph Theory
cmi2019
graph-connectivity
+
–
1
votes
1
answer
62
CMI2018-A-9
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 multi-talented ... : Find a maximum length simple cycle Find a maximum size independent set Find a maximum matching Find a maximal connected component
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 plac...
gatecse
798
views
gatecse
asked
Sep 13, 2019
Graph Theory
cmi2018
graph-theory
graph-connectivity
graph-matching
independent-set
descriptive
+
–
1
votes
2
answers
63
CMI2018-B-3
Let $G$ be a simple graph on $n$ vertices. Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected. For every $n>2$, find a graph $G_{n}$ which has exactly $n$ vertices and $\binom{n-1}{2}$ edges, and is not connected.
Let $G$ be a simple graph on $n$ vertices.Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected.For every $n>2$, find a graph $G_{n}$ which has exa...
gatecse
653
views
gatecse
asked
Sep 13, 2019
Graph Theory
cmi2018
graph-theory
graph-connectivity
descriptive
+
–
1
votes
1
answer
64
CMI2018-B-5
Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given to you by a $0-1$ 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.
Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given to you by a $0-1$ matrix $A$ of size $n\times n$ as follows. For any $1\leq i,j\...
gatecse
443
views
gatecse
asked
Sep 13, 2019
Graph Theory
cmi2018
graph-theory
undirected-graph
graph-connectivity
connected-components
descriptive
+
–
2
votes
1
answer
65
Difference between DAG and Multi-stage graph
I have trouble understanding the difference between DAG and Multi-stage graph. I know what each of them is But I think that a multi-stage graph is also a DAG. Are multi-stage graphs a special kind of DAG?
I have trouble understanding the difference between DAG and Multi-stage graph. I know what each of them isBut I think that a multi-stage graph is also a DAG. Are multi-st...
gmrishikumar
847
views
gmrishikumar
asked
Apr 28, 2019
Graph Theory
graph-theory
graph-algorithms
graph-connectivity
multi-stage-graph
directed-acyclic-graph
+
–
1
votes
1
answer
66
ISI2017-PCB-CS-1(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$.
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$.
akash.dinkar12
893
views
akash.dinkar12
asked
Apr 8, 2019
Graph Theory
isi2017-pcb-cs
engineering-mathematics
discrete-mathematics
graph-theory
graph-connectivity
descriptive
+
–
33
votes
14
answers
67
GATE CSE 2019 | Question: 12
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!$ $(n-1)!$ $1$ $\frac{(n-1)!}{2}$
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!$$(n-1)!$$1$$\frac{(n-1)!}{2}...
Arjun
21.4k
views
Arjun
asked
Feb 7, 2019
Graph Theory
gatecse-2019
engineering-mathematics
discrete-mathematics
graph-theory
graph-connectivity
1-mark
+
–
40
votes
6
answers
68
GATE CSE 2019 | Question: 38
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 minimum-weight edge crossing the cut. Which of the following statements is/are TRUE? I only II only Both I and II Neither I nor II
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...
Arjun
20.5k
views
Arjun
asked
Feb 7, 2019
Graph Theory
gatecse-2019
engineering-mathematics
discrete-mathematics
graph-theory
graph-connectivity
2-marks
+
–
0
votes
1
answer
69
doubt
what is the diameter and radius of the complete bipartite graph?
what is the diameter and radius of the complete bipartite graph?
Cristine
2.6k
views
Cristine
asked
Jan 27, 2019
Graph Theory
bipartite-graph
graph-theory
graph-connectivity
+
–
3
votes
2
answers
70
Applied Course | Mock GATE | Test 1 | Question: 36
Naveen invited seven of his friends to a party. At the party, several pairs of people shook hands, although no one shook hands with themselves or shook hands with the same person more than once. After the party, Naveen asked each of his ... positive integers. Given that his friends were truthful, how many hands did Naveen shake? $4$ $5$ $6$ $7$
Naveen invited seven of his friends to a party. At the party, several pairs of people shook hands, although no one shook hands with themselves or shook hands with the sam...
Applied Course
827
views
Applied Course
asked
Jan 16, 2019
Graph Theory
applied-course-2019-mock1
graph-theory
graph-connectivity
+
–
1
votes
1
answer
71
Applied Course | Mock GATE | Test 1 | Question: 37
The project of building $20$ roads connecting $9$ cities is under way, as outlined above. So far, only some of the $20$ roads are constructed, and the digit on each city indicates the number of constructed roads to other cities. How many complete roads are there among these cities ________
The project of building $20$ roads connecting $9$ cities is under way, as outlined above. So far, only some of the $20$ roads are constructed, and the digit on each city ...
Applied Course
863
views
Applied Course
asked
Jan 16, 2019
Graph Theory
applied-course-2019-mock1
graph-theory
graph-connectivity
numerical-answers
+
–
1
votes
1
answer
72
Applied Course | Mock GATE | Test 1 | Question: 38
Five cities P, Q, R, S, T are connected by different modes of transport as follows: P and Q connected by boat as well as rail. S and R connected by bus and boat. Q and T connected by air only. P and R connected by boat only. ... visits each of the places starting from P and gets back to P which of the following places must he visit twice? P Q R T
Five cities P, Q, R, S, T are connected by different modes of transport as follows:P and Q connected by boat as well as rail.S and R connected by bus and boat.Q and T co...
Applied Course
801
views
Applied Course
asked
Jan 16, 2019
Graph Theory
applied-course-2019-mock1
graph-theory
graph-connectivity
+
–
1
votes
1
answer
73
MadeEasy Full Length Test 2019: Graph Theory - Vertex Connectivity
The Vertex Connectivity of Graph is : 1 2 3 None
The Vertex Connectivity of Graph is :12 3None
Na462
735
views
Na462
asked
Jan 16, 2019
Graph Theory
graph-theory
graph-connectivity
made-easy-test-series
+
–
2
votes
4
answers
74
GATE Overflow | Mock GATE | Test 1 | Question: 34
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 (n-1)/2 \rceil$ $\lfloor (n+1)/2 \rfloor$ $(n-1)/2$
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 (n-1...
Ruturaj Mohanty
2.2k
views
Ruturaj Mohanty
asked
Dec 27, 2018
Graph Theory
go-mockgate-1
discrete-mathematics
graph-theory
graph-connectivity
+
–
6
votes
1
answer
75
GATE Overflow | Mock GATE | Test 1 | Question: 35
Consider the following graph. How many paths of length $4$ exist from node $A$ to node $D$? (Note: The path may have repeated vertices. You can think of it as walks in general rather than path)
Consider the following graph.How many paths of length $4$ exist from node $A$ to node $D$?(Note: The path may have repeated vertices. You can think of it as walks in gene...
Ruturaj Mohanty
3.3k
views
Ruturaj Mohanty
asked
Dec 27, 2018
Discrete Mathematics
go-mockgate-1
discrete-mathematics
graph-theory
graph-connectivity
numerical-answers
+
–
4
votes
1
answer
76
GATE Overflow | Mock GATE | Test 1 | Question: 54
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$ ... how many connected component does $G$ have, respectively? $n, 3$ $(n(n-1))/2,2$ $1, n$ $n+1, n$
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 adja...
Ruturaj Mohanty
1.1k
views
Ruturaj Mohanty
asked
Dec 27, 2018
Graph Theory
go-mockgate-1
discrete-mathematics
graph-theory
counting
graph-connectivity
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register