Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Webpage for Graph Theory:
Recent questions tagged graph-theory
0
votes
2
answers
61
#graph #degreeofgraph
Every simple, undirected, connected and acyclic graph with 50 vertices has at least two vertices of degree one.
Every simple, undirected, connected and acyclic graph with 50 vertices has at least two vertices of degree one.
Shivshankar
462
views
Shivshankar
asked
Apr 14, 2023
IS&Software Engineering
graph-theory
+
–
2
votes
0
answers
62
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
500
views
someshawasthi
asked
Mar 27, 2023
Graph Theory
graph-theory
+
–
6
votes
2
answers
63
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
989
views
GO Classes
asked
Mar 26, 2023
Graph Theory
goclasses2023-iiith-mock-1
goclasses
graph-theory
graph-connectivity
1-mark
+
–
3
votes
1
answer
64
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
557
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
65
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
605
views
admin
asked
Mar 14, 2023
Graph Theory
tifr2023
graph-theory
degree-of-graph
+
–
3
votes
0
answers
66
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
368
views
admin
asked
Mar 14, 2023
Graph Theory
tifr2023
graph-theory
graph-coloring
p-np-npc-nph
+
–
2
votes
1
answer
67
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
505
views
admin
asked
Mar 14, 2023
Graph Theory
tifr2023
graph-theory
graph-coloring
+
–
0
votes
0
answers
68
#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
389
views
Psy Duck
asked
Feb 17, 2023
Graph Theory
graph-theory
+
–
7
votes
3
answers
69
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.3k
views
admin
asked
Feb 15, 2023
Graph Theory
gatecse-2023
graph-theory
graph-coloring
multiple-selects
2-marks
+
–
1
votes
0
answers
70
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
363
views
Sahil_Lather
asked
Jan 27, 2023
Graph Theory
graph-theory
testbook-test-series
graph-planarity
+
–
0
votes
0
answers
71
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
514
views
Sahil_Lather
asked
Jan 27, 2023
Graph Theory
graph-theory
bipartite-graph
testbook-test-series
+
–
0
votes
0
answers
72
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
208
views
Sahil_Lather
asked
Jan 27, 2023
Graph Theory
graph-theory
lattice
+
–
0
votes
0
answers
73
#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
325
views
robinofautumn
asked
Jan 11, 2023
Combinatory
discrete-mathematics
graph-theory
combinatory
binary-tree
+
–
3
votes
0
answers
74
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
449
views
Kabir5454
asked
Jan 2, 2023
Graph Theory
zeal
graph-theory
discrete-mathematics
graph-coloring
numerical-answers
+
–
1
votes
1
answer
75
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
577
views
Sunnidhya Roy
asked
Dec 20, 2022
Algorithms
graph-theory
graph-algorithms
+
–
3
votes
0
answers
76
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
385
views
admin
asked
Dec 15, 2022
Graph Theory
drdocse-2022-paper1
graph-theory
bipartite-graph
graph-matching
4-marks
descriptive
+
–
1
votes
1
answer
77
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
308
views
admin
asked
Dec 15, 2022
Graph Theory
drdocse-2022-paper1
graph-theory
graph-coloring
4-marks
descriptive
+
–
1
votes
0
answers
78
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
270
views
admin
asked
Dec 15, 2022
Graph Theory
drdocse-2022-paper1
graph-theory
graph-connectivity
5-marks
descriptive
+
–
1
votes
0
answers
79
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
273
views
admin
asked
Dec 15, 2022
Graph Theory
drdocse-2022-paper1
graph-theory
graph-connectivity
5-marks
descriptive
+
–
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