Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged graph-connectivity
1
votes
2
answers
151
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 ?
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 ...
Vicky rix
1.1k
views
Vicky rix
asked
Mar 11, 2017
Graph Theory
graph-theory
discrete-mathematics
graph-connectivity
engineering-mathematics
+
–
0
votes
2
answers
152
graph theory
State TRUE or FALSE. The chromatic number of a Bi-partite graph is ALWAYS 2.
State TRUE or FALSE.The chromatic number of a Bi-partite graph is ALWAYS 2.
Vicky rix
543
views
Vicky rix
asked
Mar 11, 2017
Graph Theory
graph-theory
discrete-mathematics
graph-connectivity
engineering-mathematics
+
–
0
votes
1
answer
153
graph theory
The cardinality of the vertex-cut ( seperating set ) of a complete graph with n vertices is ___
The cardinality of the vertex-cut ( seperating set ) of a complete graph with n vertices is ___
Vicky rix
637
views
Vicky rix
asked
Mar 11, 2017
Graph Theory
graph-theory
discrete-mathematics
graph-connectivity
engineering-mathematics
+
–
0
votes
1
answer
154
graph theory
In a Bipartite graph,the size of the maximum matching is equal to the size of the minimum vertex cover ...can somebody prove this logically ?
In a Bipartite graph,the size of the maximum matching is equal to the size of the minimum vertex cover ...can somebody prove this logically ?
Vicky rix
806
views
Vicky rix
asked
Mar 10, 2017
Graph Theory
graph-theory
discrete-mathematics
graph-connectivity
engineering-mathematics
+
–
1
votes
2
answers
155
graph theory
The number of independent sets in a complete graph with n vertices is ____
The number of independent sets in a complete graph with n vertices is ____
Vicky rix
538
views
Vicky rix
asked
Mar 10, 2017
Graph Theory
graph-theory
discrete-mathematics
graph-connectivity
engineering-mathematics
+
–
1
votes
1
answer
156
graph theory
can somebody explain the logic behind this theorem ?
can somebody explain the logic behind this theorem ?
Vicky rix
341
views
Vicky rix
asked
Mar 9, 2017
Graph Theory
graph-theory
discrete-mathematics
graph-connectivity
engineering-mathematics
+
–
1
votes
2
answers
157
graph theory
Find 1) Vertex connectivity 2) Edge connectivity 3) Is it a seperable graph ? If so then find the cut-vertex
Find 1) Vertex connectivity 2) Edge connectivity 3) Is it a seperable graph ? If so then find the cut-vertex
Vicky rix
1.7k
views
Vicky rix
asked
Mar 9, 2017
Graph Theory
graph-theory
discrete-mathematics
graph-connectivity
engineering-mathematics
+
–
1
votes
1
answer
158
graph theory
Find 1) Vertex connectivity 2) Edge connectivity 3) Is it a seperable graph ? If so then find the cut-vertex 4) Is {v1,v2,v5} a cut-set ?
Find 1) Vertex connectivity 2) Edge connectivity 3) Is it a seperable graph ? If so then find the cut-vertex 4) Is {v1,v2,v5} a cut-set ?
Vicky rix
584
views
Vicky rix
asked
Mar 9, 2017
Graph Theory
graph-theory
discrete-mathematics
graph-connectivity
engineering-mathematics
+
–
1
votes
2
answers
159
graph theory
Vicky rix
450
views
Vicky rix
asked
Mar 8, 2017
Graph Theory
graph-theory
discrete-mathematics
graph-connectivity
engineering-mathematics
+
–
0
votes
1
answer
160
graph theory
Vicky rix
354
views
Vicky rix
asked
Mar 8, 2017
Graph Theory
graph-theory
discrete-mathematics
graph-connectivity
engineering-mathematics
+
–
11
votes
2
answers
161
ISI2015-PCB-C3
For a positive integer $n$, let $G = (V, E)$ be a graph, where $V = \text{{0,1}}^n$, i.e., $V$ is the set of vertices has one to one correspondence with the set of all $n$-bit binary strings and $E = \{(u,v) \mid u, v$ belongs to $V, u$ and $v$ differ in exactly one bit position$\}$. Determine size of $E$ Show that $G$ is connected
For a positive integer $n$, let $G = (V, E)$ be a graph, where $V = \text{{0,1}}^n$, i.e., $V$ is the set of vertices has one to one correspondence with the set of all $n...
Devasish Ghosh
1.4k
views
Devasish Ghosh
asked
Mar 8, 2017
Graph Theory
graph-theory
discrete-mathematics
isi2015
graph-connectivity
+
–
0
votes
1
answer
162
number of cycles in given graph:
Let N1 be the number of distinct cycles of length 3 in given graph and N2 be the number of distinct cycles of length 3, if the graph is labelled. Then N2 - N1 is __________
Let N1 be the number of distinct cycles of length 3 in given graph and N2 be the number of distinct cycles of length 3, if the graph is labelled.Then N2 - N1 is _________...
sh!va
586
views
sh!va
asked
Feb 7, 2017
Graph Theory
graph-connectivity
+
–
0
votes
1
answer
163
Graph Theory Me workbook
How S2 is correct ,I can have more than n-k edges like if n=7 and k=3 ,then K1(a-b-c-d-e) k2(f() k2(g).K1,k2,k3 are different compoinents i assumes,Now in K1 i can add one more edge between a to c or a to d and still it will be simple graph and it will have 3 components?Please help
How S2 is correct ,I can have more than n-k edges like if n=7 and k=3 ,then K1(a-b-c-d-e) k2(f() k2(g).K1,k2,k3 are different compoinents i assumes,Now in K1 i can add on...
rahul sharma 5
704
views
rahul sharma 5
asked
Feb 4, 2017
Set Theory & Algebra
discrete-mathematics
graph-connectivity
+
–
1
votes
0
answers
164
Testbook Test Series 2017: Graph Theory - Graph Connectivity
Hradesh patel
658
views
Hradesh patel
asked
Jan 26, 2017
Graph Theory
testbook-test-series
test-series
graph-theory
graph-connectivity
+
–
0
votes
1
answer
165
condition for graph disconnected
Consider a simple connected undirected graph $G$ which has $m$ vertices and $n$ edges. Which of the following condition always guarantee that after removal of those number of edges graph will be disconnected? $m-n+2$ $n-m$ $n-2$ None of the above
Consider a simple connected undirected graph $G$ which has $m$ vertices and $n$ edges. Which of the following condition always guarantee that after removal of those numbe...
iita
558
views
iita
asked
Jan 26, 2017
Graph Theory
graph-connectivity
+
–
2
votes
2
answers
166
MadeEasy Subject Test: Algorithms - Graph Connectivity
vaishali jhalani
1.1k
views
vaishali jhalani
asked
Jan 24, 2017
Graph Theory
graph-theory
graph-connectivity
made-easy-test-series
+
–
2
votes
1
answer
167
graph theory
Assumed undirected graph G is connected. G has 6vertices and 10 edges. Find the minimum number of edges whose deletion from graph G is always guarantee that it will become disconnected.
Assumed undirected graph G is connected. G has 6vertices and 10 edges. Findthe minimum number of edges whose deletion from graph G is always guaranteethat ...
sanyam53
971
views
sanyam53
asked
Jan 3, 2017
Graph Theory
graph-theory
graph-connectivity
discrete-mathematics
+
–
1
votes
2
answers
168
CMI2016-B-3
An undirected graph can be converted into a directed graph by choosing a direction for every edge. Here is an example: Show that for every undirected graph, there is a way of choosing directions for its edges so that the resulting directed graph has no directed cycles.
An undirected graph can be converted into a directed graph by choosing a direction for every edge. Here is an example:Show that for every undirected graph, there is a way...
go_editor
761
views
go_editor
asked
Dec 30, 2016
Graph Theory
cmi2016
descriptive
graph-theory
graph-connectivity
+
–
1
votes
1
answer
169
CMI2016-B-2b
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $length$ of such a path (respectively cycle) is the number of edges in the path (respectively cycle). Let $G$ be an undirected graph with minimum degree $k \geq 2$. Show that $G$ contains a simple cycle of length at least $k+1$.
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $length$ of such a path (respectively ...
go_editor
453
views
go_editor
asked
Dec 30, 2016
Graph Theory
cmi2016
graph-theory
graph-connectivity
descriptive
+
–
1
votes
2
answers
170
CMI2016-B-2a
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $\textit{length}$ of such a path (respectively cycle) is the number of edges in the path (respectively cycle). Let $G$ be an undirected graph with minimum degree $k \geq 2$. Show that $G$ contains a simple path of length at least $k$.
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $\textit{length}$ of such a path (resp...
go_editor
499
views
go_editor
asked
Dec 30, 2016
Graph Theory
cmi2016
graph-theory
descriptive
graph-connectivity
+
–
1
votes
2
answers
171
CMI2016-A-9
ScamTel has won a state government contract to connect $17$ cities by high-speed fibre optic links. Each link will connect a pair of cities so that the entire network is connected-there is a path from each city to every other city. The contract requires the network to remain ... $34$ $32$ $17$ $16$
ScamTel has won a state government contract to connect $17$ cities by high-speed fibre optic links. Each link will connect a pair of cities so that the entire network is ...
go_editor
889
views
go_editor
asked
Dec 30, 2016
Graph Theory
cmi2016
graph-theory
graph-connectivity
+
–
3
votes
1
answer
172
TIFR CSE 2016 | Part B | Question: 15
Let $G$ be an undirected graph. For a pair $(x, y)$ of distinct vertices of $G$, let $\mathsf{mincut}(x, y)$ be the least number of edges that should be delted from $G$ so that the resulting graph has no $x-y$ ... and iv are possible but neither ii nor iii ii and iv are possible but neither i not iii iii and iv are possible but neither i nor ii
Let $G$ be an undirected graph. For a pair $(x, y)$ of distinct vertices of $G$, let $\mathsf{mincut}(x, y)$ be the least number of edges that should be delted from $G$ s...
go_editor
794
views
go_editor
asked
Dec 29, 2016
Graph Theory
tifr2016
graph-theory
graph-connectivity
+
–
6
votes
1
answer
173
TIFR CSE 2016 | Part B | Question: 11
Let $n \geq 4$ be an integer. Regard the set $\mathbb{R}^n$ as a vector space over $\mathbb{R}$. Consider the following undirected graph $H$ ... inifinite number of vertices The diameter of $H$ is infinite $H$ is conneceted $H$ contains an infinite clique $H$ contains an infinite independent set
Let $n \geq 4$ be an integer. Regard the set $\mathbb{R}^n$ as a vector space over $\mathbb{R}$. Consider the following undirected graph $H$.$$ V(H) = \{S \subseteq \math...
go_editor
693
views
go_editor
asked
Dec 29, 2016
Graph Theory
tifr2016
graph-theory
graph-connectivity
+
–
2
votes
2
answers
174
graph theory
thor
1.3k
views
thor
asked
Dec 28, 2016
Graph Theory
graph-theory
graph-connectivity
euler-graph
+
–
3
votes
3
answers
175
TIFR CSE 2016 | Part A | Question: 14
A $diagonal$ in a polygon is a straight line segment that connects two non-adjacent vertices, and is contained in the interior of the polygon (except for its points). Two such diagonals are said to cross if they have a point in common in the interior of the polygon. In one such ... the information given $\frac{n}{2}-2$ $\frac{n}{4}-1$ $n-4$ $n^2 - 9.5 n +22$
A $diagonal$ in a polygon is a straight line segment that connects two non-adjacent vertices, and is contained in the interior of the polygon (except for its points). Two...
go_editor
852
views
go_editor
asked
Dec 28, 2016
Graph Theory
tifr2016
graph-theory
graph-connectivity
+
–
8
votes
5
answers
176
TIFR CSE 2016 | Part A | Question: 2
Consider the graph shown below: The following experiment is performed using this graph. First, an edge $e =\{i,j\}$ of the graph is chosen uniformly at random from the set of $9$ possibilities. Next, a common neighbour $k$ of $i$ and $j$ is chosen, again uniformly from the set of ... $\frac{1}{6}$ $\frac{1}{4}$ $\frac{1}{3}$ $\frac{2}{3}$ $\frac{5}{6}$
Consider the graph shown below:The following experiment is performed using this graph. First, an edge $e =\{i,j\}$ of the graph is chosen uniformly at random from the set...
go_editor
1.0k
views
go_editor
asked
Dec 26, 2016
Graph Theory
tifr2016
graph-theory
graph-connectivity
probability
+
–
54
votes
7
answers
177
TIFR CSE 2017 | Part B | Question: 12
An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a direction for the edges so that there are no directed cycles? $n$ $\frac{n(n-1)}{2}$ $n!$ $2^n$ $2^m, \: \text{ where } m=\frac{n(n-1)}{2}$
An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a d...
go_editor
6.5k
views
go_editor
asked
Dec 23, 2016
Graph Theory
tifr2017
graph-theory
graph-connectivity
+
–
15
votes
4
answers
178
GATE CSE 1988 | Question: 2xvi
Write the adjacency matrix representation of the graph given in below figure.
Write the adjacency matrix representation of the graph given in below figure.
go_editor
3.9k
views
go_editor
asked
Dec 19, 2016
Graph Theory
gate1988
descriptive
graph-theory
graph-connectivity
+
–
1
votes
1
answer
179
graph
Which of the following statements is/are TRUE? [P] Every disconnected graph has an isolated vertex [Q] A graph is connected if and only if some vertex is connected to all other vertices [R] The edge set of every closed trail can be partitioned into edge sets of cycles [S] If a maximal trail in a graph is not closed, then its endpoints have odd degree
Which of the following statements is/are TRUE?[P] Every disconnected graph has an isolated vertex[Q] A graph is connected if and only if some vertex is connected to all o...
Neal Caffery
2.7k
views
Neal Caffery
asked
Dec 12, 2016
Graph Theory
graph-theory
engineering-mathematics
graph-connectivity
+
–
0
votes
0
answers
180
Graph theory
proof :- A connected graph any two paths of maximum length share at least one vertex
proof :- A connected graph any two paths of maximum length share at least one vertex
Neal Caffery
233
views
Neal Caffery
asked
Dec 12, 2016
Graph Theory
graph-theory
graph-connectivity
discrete-mathematics
+
–
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