The GATE Grind

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.