Use the proof of Cayleys Theorem to find the spanning tree a

Use the proof of Cayley\'s Theorem to find the spanning tree associated with the vector

Solution

According to cayley\'s theorem, \"Every group is isomorphic to group of permutations.\"

Isomorphism is a bijective homomorphism

Let n denote the number of vertices of the input graph. K_n denote the complete graph with n vertices

Eg: For a square with for vertex viz, 1,2,3,4 we have 16 spanning trees.Each spanning tree is associated with a two number sequence.

(1,1) (1,2),(1,3),(1,4)

(2,1),(2,2),(2,3),(2,4)

(3,1)(3,2)(3,3)(3,4)

(4,1)(4,2)(4,3|)4,4)

Thus nof spanning trees in K_n is n^n-2 for all n >=2