Graph Theory Proof Needed Chapter Text httpsdrivegooglecomfi

Graph Theory Proof Needed:

Chapter Text: https://drive.google.com/file/d/0BzHAyUGPRvJIMmljX2dzSzktS2M/view?usp=sharing

Solution

The logic below can be tightened up by enumerating the number of trees in each class (stars, double stars, paths) and enumerating the paths of each specified type.

(a) Suppose the Pr¨ufer code is a string of i copies of j. This means that every leaf of the tree must have j as its unique neighbor. So the graph must be an (i+2)-star (i.e., K1,i+1) on i + 2 vertices. In other words, there are i + 1 leaves and one vertex (labelled j) of degree i + 1.

(b) This is very similar to the first case. Now, there are exactly two non-leafs in the tree.

(c) Let n denote the number of vertices of the tree. Suppose there is a vertex i of degree at least 3. After the n 2 leaf removals have been made, there are two vertices left, each of degree 1. But this implies that i has to appear at least twice in the Pr¨ufer code (it’s either one of the two vertices remaining at the end or it gets removed as a leaf at some point). So any tree with a Pr¨ufer code consisting of distinct numbers must only have vertices of degree 1 or 2. The only such trees are paths. Conversely, by the same logic as above, any path has a Pr¨ufer code without repeats