Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged graph-connectivity
5
votes
1
answer
31
GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 6
Let $\text{G = (V, E)}$ be a finite directed acyclic graph with $|\text{E}| > 0.$ Which of the following is not necessarily true? $\text{G}$ has a vertex with no incoming edge. $\text{G}$ has a ... no outgoing edge. $\text{G}$ has an isolated vertex, that is, one with neither an incoming edge nor an outgoing edge. None
Let $\text{G = (V, E)}$ be a finite directed acyclic graph with $|\text{E}| 0.$ Which of the following is not necessarily true?$\text{G}$ has a vertex with no incoming e...
GO Classes
610
views
GO Classes
asked
May 11, 2022
Graph Theory
goclasses2024-dm-5-weekly-quiz
goclasses
graph-theory
graph-connectivity
1-mark
+
–
3
votes
1
answer
32
GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 7
A Hamiltonian circuit in a graph is a closed path that visits every vertex in the graph exactly once. A Hamiltonian circuit ends up at the vertex from where it started. If a graph has some Hamiltonian circuit, then the graph is called a ... following is/are a hamiltonian graph? $\text{G1}$ $\text{G2}$ $\text{G3}$ $\text{G4}$
A Hamiltonian circuit in a graph is a closed path that visits every vertex in the graph exactly once. A Hamiltonian circuit ends up at the vertex from where it started.If...
GO Classes
558
views
GO Classes
asked
May 11, 2022
Graph Theory
goclasses2024-dm-5-weekly-quiz
goclasses
graph-theory
graph-connectivity
multiple-selects
1-mark
+
–
4
votes
1
answer
33
GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 8
Let $\text{G}$ be a simple graph where $\text{V(G)} = \{1, 2, \dots , 100\}$ and there is an edge between two distinct vertices $a$ and $b$ iff $a$ divides $b.$ Which of the following statements are true for $\text{G}?$ ... $\text{G}$ is $1.$ $\text{G}$ is connected. The diameter of $\text{G}$ is $6.$
Let $\text{G}$ be a simple graph where $\text{V(G)} = \{1, 2, \dots , 100\}$ and there is an edge between two distinct vertices $a$ and $b$ iff $a$ divides $b.$Which of t...
GO Classes
374
views
GO Classes
asked
May 11, 2022
Graph Theory
goclasses2024-dm-5-weekly-quiz
goclasses
graph-theory
graph-connectivity
multiple-selects
1-mark
+
–
4
votes
1
answer
34
GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 11
Let $\text{K}(4,6)$ be the complete bipartite graph on $10$ vertices, having $4$ vertices in one part and having $6$ ... is a complete graph. Either $\text{K}(m,n)$ OR complement of $\text{K}(m,n)$ is dis-connected.
Let $\text{K}(4,6)$ be the complete bipartite graph on $10$ vertices, having $4$ vertices in one part and having $6$ vertices in another part. Which of the following is/a...
GO Classes
367
views
GO Classes
asked
May 11, 2022
Graph Theory
goclasses2024-dm-5-weekly-quiz
goclasses
graph-theory
graph-connectivity
multiple-selects
2-marks
+
–
3
votes
1
answer
35
GO Classes Test Series 2024 | Discrete Mathematics | Test 5 | Question: 23
The height of a rooted tree is the maximum height of any leaf. The length of the unique path from a leaf of the tree to the root is, by definition, the height of that leaf. A rooted tree in which each non-leaf vertex has at ... maximum height $h = L-1.$ It is possible to have a binary tree with $35$ leaves and height $100.$
The height of a rooted tree is the maximum height of any leaf. The length of the unique path from a leaf of the tree to the root is, by definition, the height of that lea...
GO Classes
633
views
GO Classes
asked
May 11, 2022
Graph Theory
goclasses2024-dm-5-weekly-quiz
goclasses
graph-theory
graph-connectivity
multiple-selects
2-marks
+
–
19
votes
5
answers
36
GATE CSE 2022 | Question: 20
Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .
Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .
Arjun
8.8k
views
Arjun
asked
Feb 15, 2022
Graph Theory
gatecse-2022
numerical-answers
graph-theory
graph-connectivity
1-mark
+
–
14
votes
3
answers
37
GATE CSE 2022 | Question: 27
Consider a simple undirected unweighted graph with at least three vertices. If $\textit{A}$ is the adjacency matrix of the graph, then the number of $3–$cycles in the graph is given by the trace of $\textit{A}^{3}$ $\textit{A}^{3}$ divided by $2$ $\textit{A}^{3}$ divided by $3$ $\textit{A}^{3}$ divided by $6$
Consider a simple undirected unweighted graph with at least three vertices. If $\textit{A}$ is the adjacency matrix of the graph, then the number of $3–$cycles in the g...
Arjun
7.5k
views
Arjun
asked
Feb 15, 2022
Graph Theory
gatecse-2022
graph-theory
graph-connectivity
2-marks
+
–
16
votes
4
answers
38
GATE CSE 2022 | Question: 42
Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices? The diagonal entries of $A^{2}$ ... . If there is at least a $1$ in each of $A\text{'s}$ rows and columns, then the graph must be connected.
Which of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices?The diagonal entries of $A^{2}$ are the degrees of t...
Arjun
7.4k
views
Arjun
asked
Feb 15, 2022
Graph Theory
gatecse-2022
graph-theory
graph-connectivity
multiple-selects
2-marks
+
–
0
votes
2
answers
39
Self Doubt
Why is the vertex connectivity of a graph always less than or equal to its edge connectivity?
Why is the vertex connectivity of a graph always less than or equal to its edge connectivity?
raja11sep
495
views
raja11sep
asked
Jan 5, 2022
Graph Theory
graph-theory
graph-connectivity
+
–
3
votes
1
answer
40
TIFR CSE 2021 | Part B | Question: 12
Let $G$ be an undirected graph. For any two vertices $u, v$ in $G$, let $\textrm{cut} (u, v)$ be the minimum number of edges that should be deleted from $G$ so that there is no path between $u$ and $v$ in the resulting graph. Let $a, b, c, d$ be $4$ ... $\textrm{cut} (b,d) = 2$, $\textrm{cut} (b,c) = 2$ and $\textrm{cut} (c,d) = 1$
Let $G$ be an undirected graph. For any two vertices $u, v$ in $G$, let $\textrm{cut} (u, v)$ be the minimum number of edges that should be deleted from $G$ so that there...
soujanyareddy13
581
views
soujanyareddy13
asked
Mar 25, 2021
Graph Theory
tifr2021
graph-theory
graph-connectivity
+
–
35
votes
6
answers
41
GATE CSE 2021 Set 1 | Question: 36
Let $G=(V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as: $\text{diam}(G)=\displaystyle \max_{u,v\in V} \{\text{the length of shortest path between $u$ and $v$}\}$ Let $M$ be the adjacency matrix of $G$. Define graph $G_2$ ... $\text{diam}(G_2) = \text{diam}(G)$ $\text{diam}(G)< \text{diam}(G_2)\leq 2\; \text{diam}(G)$
Let $G=(V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as:$$\text{diam}(G)=\displaystyle \max_{u,v\in V} \{\text{the length of shortes...
Arjun
9.9k
views
Arjun
asked
Feb 18, 2021
Graph Theory
gatecse-2021-set1
graph-theory
graph-connectivity
2-marks
+
–
5
votes
1
answer
42
GATE Overflow Test Series | Mock GATE | Test 4 | Question: 22
In a graph, a vertex is called an articulation point if removing it and all the edges associated with it results in the increase of the number of connected components in the graph. Let $G$ be a graph contain $10$ vertices, if $G$ has $8$ articulation points then what must be the number of edges in graph $G$? $45$ $10$ $9$ $8$
In a graph, a vertex is called an articulation point if removing it and all the edges associated with it results in the increase of the number of connected components in ...
gatecse
361
views
gatecse
asked
Feb 1, 2021
Graph Theory
go2025-mockgate-4
graph-theory
graph-connectivity
+
–
7
votes
1
answer
43
GATE Overflow Test Series | Mock GATE | Test 3 | Question: 37
How many walks of length four are there from $a$ to $c$ in the simple graph $G$?
How many walks of length four are there from $a$ to $c$ in the simple graph $G$?
gatecse
784
views
gatecse
asked
Jan 26, 2021
Graph Theory
go2025-mockgate-3
numerical-answers
graph-theory
graph-connectivity
+
–
2
votes
2
answers
44
NIELIT Scientific Assistant A 2020 November: 19
What is the total number of ways to reach from $A$ to $B$ in the network given? $12$ $16$ $20$ $22$
What is the total number of ways to reach from $A$ to $B$ in the network given?$12$$16$$20$$22$
gatecse
1.0k
views
gatecse
asked
Dec 8, 2020
Graph Theory
nielit-sta-2020
graph-theory
graph-connectivity
+
–
1
votes
1
answer
45
GATE Overflow Test Series | Mixed Subjects | Test 3 | Question: 29
Which of the following is/are possible for unlabelled trees/graphs? (Mark all the appropriate choices) Two different trees with the same number of vertices and the same number of edges. Two different simple graphs with $8$ vertices all of ... $5$ vertices all of degree $4.$ Two different graphs with $7$ vertices all of degree $3.$
Which of the following is/are possible for unlabelled trees/graphs? (Mark all the appropriate choices)Two different trees with the same number of vertices and the same nu...
gatecse
135
views
gatecse
asked
Oct 15, 2020
Graph Theory
go2025-mix-3
graph-connectivity
multiple-selects
+
–
1
votes
1
answer
46
GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 1
If $G$ is a simple graph with $16$ edges and $\overline{G}$ has $12$ edges, how many vertices does the complement graph $\overline{G}$ have?
If $G$ is a simple graph with $16$ edges and $\overline{G}$ has $12$ edges, how many vertices does the complement graph $\overline{G}$ have?
gatecse
195
views
gatecse
asked
Sep 14, 2020
Graph Theory
go2025-dm-4
numerical-answers
graph-connectivity
+
–
4
votes
1
answer
47
GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 3
The number of possible connected simple graphs with $3$ labelled vertices is ________
The number of possible connected simple graphs with $3$ labelled vertices is ________
gatecse
321
views
gatecse
asked
Sep 14, 2020
Graph Theory
go2025-dm-4
numerical-answers
graph-connectivity
+
–
4
votes
2
answers
48
GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 6
Which of the following is/are correct? $S_1:$ A connected graph of at least $2$ vertices has an Euler circuit if and only if degree of every vertex is even. $S_2:$ A connected graph has an Euler path if and only if there are at most two vertices with odd degree. $S_1$ only $S_2$ only Both $S_1$ and $S_2$ Neither $S_1$ nor $S_2$
Which of the following is/are correct?$S_1:$ A connected graph of at least $2$ vertices has an Euler circuit if and only if degree of every vertex is even.$S_2:$ A connec...
gatecse
340
views
gatecse
asked
Sep 14, 2020
Graph Theory
go2025-dm-4
graph-connectivity
euler-graph
+
–
1
votes
1
answer
49
GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 7
Suppose a simple graph has $45$ edges, $5$ vertices of degree $6$, and all others of degree $5$. How many vertices does the graph have?
Suppose a simple graph has $45$ edges, $5$ vertices of degree $6$, and all others of degree $5$. How many vertices does the graph have?
gatecse
128
views
gatecse
asked
Sep 14, 2020
Graph Theory
go2025-dm-4
numerical-answers
graph-connectivity
degree-of-graph
+
–
3
votes
1
answer
50
GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 8
The maximum number of edges in a disconnected graph having $12$ vertices is _______
The maximum number of edges in a disconnected graph having $12$ vertices is _______
gatecse
158
views
gatecse
asked
Sep 14, 2020
Graph Theory
go2025-dm-4
numerical-answers
graph-connectivity
+
–
2
votes
2
answers
51
GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 10
The maximum number of edges a graph with $45$ vertices, and $15$ connected components is ________
The maximum number of edges a graph with $45$ vertices, and $15$ connected components is ________
gatecse
183
views
gatecse
asked
Sep 14, 2020
Graph Theory
go2025-dm-4
numerical-answers
graph-connectivity
+
–
Page:
« prev
1
2
3
4
5
6
7
...
9
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register