3. (20%) A Prfer sequence of length n- 2, where n > 2, is any sequence...

Transcribed Image Text:

3. (20%) A Prüfer sequence of length n- 2, where n > 2, is any sequence of integers between 1 and n with repetitions allowed. (a) Prove that there are n"-2 Prüfer sequences of length n- 2. (5%) (b) Let K, denote a complete graph of n vertices (i.e., each pair of vertices is connected by an edge). Prove that there is a one-to-one correpsondce (bijection) between the set of spanning tree of Kn and the set of Prüfer sequences of length n – 2. (15%) 3. (20%) A Prüfer sequence of length n- 2, where n > 2, is any sequence of integers between 1 and n with repetitions allowed. (a) Prove that there are n"-2 Prüfer sequences of length n- 2. (5%) (b) Let K, denote a complete graph of n vertices (i.e., each pair of vertices is connected by an edge). Prove that there is a one-to-one correpsondce (bijection) between the set of spanning tree of Kn and the set of Prüfer sequences of length n – 2. (15%)