Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Webpage for Graph Theory:
Recent questions tagged graph-theory
2
votes
0
answers
61
discrete mathematics
The maximum number of edges possible in a graph G with 9 vertices which is 3 colourable is equal to A 24 B 27 C 36 D None of the above
The maximum number of edges possible in a graph G with 9 vertices which is 3 colourable is equal toA 24B 27C 36D None of the above
someshawasthi
479
views
someshawasthi
asked
Mar 27, 2023
Graph Theory
graph-theory
+
–
6
votes
2
answers
62
GO Classes 2023 | IIITH Mock Test 1 | Question: 3
Let $\text{G}$ be a graph on $10$ vertices. We delete one vertex from $\text{G}.$ Since we have $10$ vertices, hence we get $10$ different subgraphs depending on which vertex we have deleted. Suppose that the number of edges in the vertex-deleted subgraphs of ... $\text{G}?$ $14$ $16$ $13$ $15$
Let $\text{G}$ be a graph on $10$ vertices. We delete one vertex from $\text{G}.$ Since we have $10$ vertices, hence we get $10$ different subgraphs depending on which ve...
GO Classes
795
views
GO Classes
asked
Mar 26, 2023
Graph Theory
goclasses2023-iiith-mock-1
goclasses
graph-theory
graph-connectivity
1-mark
+
–
3
votes
1
answer
63
GO Classes 2023 | IIITH Mock Test 1 | Question: 42
Which of the following statements are correct? The complement of a simple disconnected graph must be connected. The complement of a simple connected graph must be disconnected. The complement of complete bipartite graph $\text{K}(4,6)$ has $10$ components. ... its complement. Then $\text{G}$ must have $4k$ or $4k + 1$ vertices for some integer $k.$
Which of the following statements are correct?The complement of a simple disconnected graph must be connected.The complement of a simple connected graph must be disconnec...
GO Classes
460
views
GO Classes
asked
Mar 26, 2023
Graph Theory
goclasses2023-iiith-mock-1
goclasses
graph-theory
graph-isomorphism
multiple-selects
1-mark
+
–
5
votes
0
answers
64
TIFR CSE 2023 | Part B | Question: 10
A $d$-regular graph is one in which every vertex has degree $d$. Also, a minimum cut in a graph is a smallest set of edges which, upon removal, disconnects the graph, so that there are vertices in the resulting graph with no path between them. We are given two ... in $G_{2}$. Which of the following must be the size of this minimum cut? $0$ $1$ $2$ $3$ $4$
A $d$-regular graph is one in which every vertex has degree $d$. Also, a minimum cut in a graph is a smallest set of edges which, upon removal, disconnects the graph, so ...
admin
578
views
admin
asked
Mar 14, 2023
Graph Theory
tifr2023
graph-theory
degree-of-graph
+
–
3
votes
0
answers
65
TIFR CSE 2023 | Part B | Question: 12
A graph $G=(V, E)$ is said to be $k$-colourable if the set $V$ of vertices can be coloured with $k$ colours such that no edge has both its endpoints of the same colour. It is known that the following language $\text{3COL}$ is $\text{NP}$-complete. \[ 3 \ ... $\text{(P1), (P3)}$and $\text{(P4)}$ Only problems $\text{(P1), (P2)}$and $\text{(P4)}$
A graph $G=(V, E)$ is said to be $k$-colourable if the set $V$ of vertices can be coloured with $k$ colours such that no edge has both its endpoints of the same colour. I...
admin
348
views
admin
asked
Mar 14, 2023
Graph Theory
tifr2023
graph-theory
graph-coloring
p-np-npc-nph
+
–
2
votes
1
answer
66
TIFR CSE 2023 | Part B | Question: 13
You have a regular tetrahedron and $4$ distinct colours. You wish to paint the faces of the tetrahedron such that each face gets a different colour. How many ways can you colour the tetrahedron? Recall that a regular tetrahedron is a three-dimensional ... considered the same if they are identical after possibly rotating the tetrahedron. $24$ $12$ $8$ $6$ $2$
You have a regular tetrahedron and $4$ distinct colours. You wish to paint the faces of the tetrahedron such that each face gets a different colour. How many ways can you...
admin
465
views
admin
asked
Mar 14, 2023
Graph Theory
tifr2023
graph-theory
graph-coloring
+
–
0
votes
0
answers
67
#Graphs #Self_Doubt #Connectivity
What is a biconnected componenet?Does it always include V-V’ where V’ represent the set of articulation points of a graph G?
What is a biconnected componenet?Does it always include V-V’ where V’ represent the set of articulation points of a graph G?
Psy Duck
380
views
Psy Duck
asked
Feb 17, 2023
Graph Theory
graph-theory
+
–
7
votes
3
answers
68
GATE CSE 2023 | Question: 45
Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=\{1,2, \ldots\}$ denote the set of all possible colors. Color the vertices ... $\Delta(G)$. The number of colors used is equal to the chromatic number of $G$.
Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=...
admin
8.1k
views
admin
asked
Feb 15, 2023
Graph Theory
gatecse-2023
graph-theory
graph-coloring
multiple-selects
2-marks
+
–
1
votes
0
answers
69
TestBook graph theory question
If G is a simple planar connected graph with 5 vertices, how many edges in maximum can be there in the given graph?
If G is a simple planar connected graph with 5 vertices, how many edges in maximum can be there in the given graph?
Sahil_Lather
354
views
Sahil_Lather
asked
Jan 27, 2023
Graph Theory
graph-theory
testbook-test-series
graph-planarity
+
–
0
votes
0
answers
70
TestBook graph theory questions
Let Gn be the complete bipartite graph K13, 17 then the chromatic number of G̅n is _____ (G̅n is complement of Gn and n = 30) A 13 B 17 C n(n−1)2−13×17 D n(n−1)2−2
Let Gn be the complete bipartite graph K13, 17 then the chromatic number of G̅n is _____ (G̅n is complement of Gn and n = 30)A13B17Cn(n−1)2−13×17Dn(n−1)2−2
Sahil_Lather
490
views
Sahil_Lather
asked
Jan 27, 2023
Graph Theory
graph-theory
bipartite-graph
testbook-test-series
+
–
0
votes
0
answers
71
TestBook Hasse Diagram question to find GLB
If [P(A); ⊆] is a lattice where A = {x, y} and P(A) is the power set then what is the sum of element in Greatest Lower Bound (GLB) set of given lattice? x + y x y 0
If [P(A); ⊆] is a lattice where A = {x, y} and P(A) is the power set then what is the sum of element in Greatest Lower Bound (GLB) set of given lattice?x + y xy0
Sahil_Lather
195
views
Sahil_Lather
asked
Jan 27, 2023
Graph Theory
graph-theory
lattice
+
–
0
votes
0
answers
72
#selfdoubt
Let n players enter a chess tournament. How many tournament trees are possible? RULES: a player is eliminated after one loss and games are played until only one entrant is left(assume no ties) My approach: (please check if it is correct) there are 3 possible binary tree skeletons w.r.t ... )C2 * (n-4)C2 *...*1} * 2^(n-1) similarly we can do the remaining cases. Is the above method right?
Let n players enter a chess tournament. How many tournament trees are possible?RULES: a player is eliminated after one loss and games are played until only one entrant is...
robinofautumn
317
views
robinofautumn
asked
Jan 11, 2023
Combinatory
discrete-mathematics
graph-theory
combinatory
binary-tree
+
–
3
votes
0
answers
73
graph theory
Let $G=(V,E)$ where $V=\left \{ 1,2,3,4,.....,150\right \}$ and $(u,v) \in E$ if either $(u mod v) =0$ or $(v mod u)=0$.The Chromatic number of G is ?
Let $G=(V,E)$ where $V=\left \{ 1,2,3,4,.....,150\right \}$ and $(u,v) \in E$ if either $(u mod v) =0$ or $(v mod u)=0$.The Chromatic number of G is ?
Kabir5454
427
views
Kabir5454
asked
Jan 2, 2023
Graph Theory
zeal
graph-theory
discrete-mathematics
graph-coloring
numerical-answers
+
–
1
votes
1
answer
74
Self Doubt
Does BFS and DFS traversal sequence exist for disconnected graphs? Is yes can you please give a dry run of the algorithm on a disconnected graph? According to me it should not exist as there is no edge to visit certain vertices of a different graph component from the source vertex in a disconnected graph. There is no absolute answer I could find online to this question.
Does BFS and DFS traversal sequence exist for disconnected graphs? Is yes can you please give a dry run of the algorithm on a disconnected graph?According to me it should...
Sunnidhya Roy
519
views
Sunnidhya Roy
asked
Dec 20, 2022
Algorithms
graph-theory
graph-algorithm
+
–
3
votes
0
answers
75
DRDO CSE 2022 Paper 1 | Question: 9
Count the number of perfect matchings in the bipartite graph whose adjacency matrix $\text{A}$ is as follows. \[\left[\begin{array}{lll} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{array}\right]\]
Count the number of perfect matchings in the bipartite graph whose adjacency matrix $\text{A}$ is as follows.\[\left[\begin{array}{lll}1 & 1 & 0 \\0 & 1 & 1 \\1 & 1 & 1\e...
admin
374
views
admin
asked
Dec 15, 2022
Graph Theory
drdocse-2022-paper1
graph-theory
bipartite-graph
graph-matching
4-marks
descriptive
+
–
1
votes
0
answers
76
DRDO CSE 2022 Paper 1 | Question: 10
Given a tree $\text{T}$ and $\lambda \geq 2$ colours $\left(c_{1}, c_{2}, \ldots, c_{\lambda}\right),$ how many proper colourings of the tree $\text{T}$ are possible?
Given a tree $\text{T}$ and $\lambda \geq 2$ colours $\left(c_{1}, c_{2}, \ldots, c_{\lambda}\right),$ how many proper colourings of the tree $\text{T}$ are possible?
admin
277
views
admin
asked
Dec 15, 2022
Graph Theory
drdocse-2022-paper1
graph-theory
graph-coloring
4-marks
descriptive
+
–
1
votes
0
answers
77
DRDO CSE 2022 Paper 1 | Question: 11
Consider the following graph. Find closeness centrality of $\text{‘A’}$ node.
Consider the following graph.Find closeness centrality of $\text{‘A’}$ node.
admin
260
views
admin
asked
Dec 15, 2022
Graph Theory
drdocse-2022-paper1
graph-theory
graph-connectivity
5-marks
descriptive
+
–
1
votes
0
answers
78
DRDO CSE 2022 Paper 1 | Question: 13
Consider the following graph. Which nodes form the cliques of size $3?$
Consider the following graph.Which nodes form the cliques of size $3?$
admin
268
views
admin
asked
Dec 15, 2022
Graph Theory
drdocse-2022-paper1
graph-theory
graph-connectivity
5-marks
descriptive
+
–
0
votes
1
answer
79
graph theory ,discrete math
how many subgraph with atleast 1 vertex does k2 have? (graph theory question)
how many subgraph with atleast 1 vertex does k2 have? (graph theory question)
shuham kumar
391
views
shuham kumar
asked
Nov 18, 2022
Mathematical Logic
discrete-mathematics
graph-theory
+
–
Page:
« prev
1
2
3
4
5
6
7
8
...
30
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register