In the Prufer code for a certain tree T, seven numbers appear twice each, one number appears three times, and no other number appears. Determine (with proof) the number of leaves that T contains.
In the Prufer code for a certain tree T, seven numbers appear twice each, one number appears three times, and no other number appears. Determine (with proof) the number of leaves that T contains.
The code helps in encoding a labelled tree having n vertices, by using a sequence of integers in the interval . The encoding used acts as a bijection between all spanning trees of the numerical sequences and a complete graph.
Given,
code- Seven numbers appear twice each, one number appears three times and no other number appears.
By using the given data it is clear that the length of the sequence (or code) =17
Therefore,
(since the sequence used is of integers, there are 2 more vertices than the number of sequence)
Since there is one number that appears three time, let that number be
Also there are seven numbers that appear twice, let these numbers be
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
