GATE 2024 CS (CS1) – Question 34
Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 1 mark · Numerical answer
The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is _________
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 16
Explanation
By Cayley's formula, the number of labelled spanning trees of K_n is n^(n−2) = 4² = 16.
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
- GATE 2024 CS (CS1) Q51 – The chromatic number of a graph is the minimum number of colours used in a proper…
- GATE 2024 CS (CS2) Q17 – Let A be the adjacency matrix of a simple undirected graph G. Suppose A is its own…
- GATE 2024 CS (CS2) Q51 – Let G be an undirected connected graph in which every edge has a positive integer weight.…
- GATE 2024 CS (CS2) Q60 – The chromatic number of a graph is the minimum number of colours used in a proper…
- GATE 2023 CS Q55 – Let G be a simple, finite, undirected graph with vertex set \v 1,,v n\. Let (G) denote the…
- GATE 2022 CS Q30 – Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the…
All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →