Question 86
An undirected graph G has 15 vertices and 20 edges. What is the sum of the degrees of all vertices in G?
Detailed Solution
Sum of degrees = 2 * |E| = 2 * 20 = 40.
✓ 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 87
Calculate the total number of edges in a complete undirected graph $K_{8}$ with 8 vertices.
Detailed Solution
$Edges = n * (n - 1) / 2 = 8 * 7 / 2 = 28.$
✓ Saved
Question 88
How many distinct spanning trees can be formed from a complete labeled graph $K_{5}$ (using Cayley's Formula)?
Detailed Solution
$Cayley's Formula = n^{n-2} = 5^{5-2} = 5^3 = 125.$
✓ Saved
Question 89
A simple undirected connected planar graph has 10 vertices and 15 edges. How many faces (regions) does it divide the plane into?
Detailed Solution
$Euler's formula: V - E + F = 2 => 10 - 15 + F = 2 => -5 + F = 2 => F = 7.$
✓ Saved
Question 90
What is the maximum number of edges in a simple bipartite graph with 12 vertices?
Detailed Solution
Max edges in bipartite graph with 12 vertices = (12/2) * (12/2) = 6 * 6 = 36.
✓ Saved