Question 96
A tree has 20 vertices. How many edges does it contain?
Detailed Solution
A tree with V vertices contains exactly V - 1 edges = 20 - 1 = 19.
✓ Saved
GATE CSE Graphs & Graph Algorithms – Data Structures Practice Test | Set 1
Your score
0/100
0 answered
Correct 0
Incorrect 0
Unanswered 100
Accuracy 0%
Question 97
How many edges are in a complete bipartite graph $K_{4,5}$?
Detailed Solution
Edges in $K_{m,n} = m \cdot n = 4 \cdot 5 = 20$.
✓ Saved
Question 98
In a directed graph with 8 vertices, the sum of in-degrees of all vertices is 14. What is the total number of directed edges in the graph?
Detailed Solution
The sum of in-degrees of all vertices in a directed graph is equal to the total number of directed edges |E| = 14.
✓ Saved
Question 99
What is the total number of edges in a wheel graph $W_{6}$ with 6 vertices?
Detailed Solution
Total edges in $W_{n} = 2 \cdot (n - 1) = 2 \cdot (6 - 1) = 2 \cdot 5 = 10$.
✓ Saved
Question 100
Suppose a graph has 5 connected components where component sizes are 2, 3, 4, 1, 1 vertices. If each component is a complete graph, what is the total number of edges in the graph?
Detailed Solution
Edges in $K_{2} = 1$, $K_{3} = 3$, $K_{4} = 6$, $K_{1} = 0$, $K_{1} = 0$. Total edges = 1 + 3 + 6 + 0 + 0 = 10.
✓ Saved