Success TrackerSuccess Tracker
Log inSign up

GATE CS 2024 Set 1 — Question 34

NAT+1 / -0EasyTrees & Spanning TreesGraph Theory (Math)Engineering Mathematics

Engineering Mathematics → Graph Theory (Math) → Trees & Spanning Trees

Last updated

Question

The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is _________

Correct answer

16 to 16

Solution

The number of spanning trees in a complete graph with nn vertices (KnK_n) is given by Cayley's formula:Number of spanning trees=nn−2\text{Number of spanning trees} = n^{n-2}Given n=4n = 4:44−2=42=164^{4-2} = 4^2 = 16

More questions on Graph Theory (Math)

2024 Set 2 Q3In an engineering college of 10,000 students, 1,500 like neither their core branches nor other…2024 Set 1 Q11Let f:R→Rf: \mathbb{R} \rightarrow \mathbb{R} be a function such that…2024 Set 2 Q12Let pp and qq be the following propositions: pp: Fail grade can be given. qq: Student scores…2024 Set 1 Q12The product of all eigenvalues of the matrix…2024 Set 1 Q14Consider a permutation sampled uniformly at random from the set of all permutations of…

Practice GATE CS PYQs with adaptive difficulty

Timed practice, skill tracking, and AI explanations — free to start.

Start practicing free