Solving 3-1 Trees: Proving Even # of Vertices & Finding Leaf #s

[leilei]

please help solve tree problem...

A tree is called a 3-1 tree if every vertex in the tress has degree equal to either 3 or 1.
1. Draw all 3-1 trees with four or fewer vertices of degree 3.
2. Prove that a 3-1 tree must have an even number of vertices.
3. Find a formula for the number of leaves in a 3-1 tree that has exactly m vertices.

 

[quantumdude]

And what are your thoughts on the matter?

 

[Architeuthis Dux]

1. To draw all 3-1 trees with four or fewer vertices of degree 3, we can start by drawing a root node with three children, each of which has one child. This forms a 3-1 tree with four vertices. We can then add another level by drawing two more nodes connected to the first level, each with three children and one child respectively. This forms a 3-1 tree with five vertices. We can continue this pattern to draw all possible 3-1 trees with four or fewer vertices of degree 3.

2. To prove that a 3-1 tree must have an even number of vertices, we can use the fact that the sum of the degrees of all vertices in a tree is equal to twice the number of edges. In a 3-1 tree, each vertex has degree either 3 or 1. Let's say there are n vertices in the tree. Then the sum of the degrees of all vertices can be written as 3n + (n-2), since there are n-2 vertices with degree 1 and each of the remaining n vertices has degree 3. This can be simplified to 4n - 2. Since this must be equal to twice the number of edges, which is 2(n-1), we can set up an equation: 4n - 2 = 2(n-1). Solving for n, we get n = 2. This means that a 3-1 tree must have an even number of vertices (specifically, 2 or a multiple of 2).

3. To find a formula for the number of leaves in a 3-1 tree with exactly m vertices, we can use the fact that the sum of the degrees of all vertices is equal to twice the number of edges. In a 3-1 tree, the sum of the degrees of all vertices can be written as 3m + (m-2) = 4m - 2. Since each leaf has degree 1, the number of leaves can be written as l = m - 2. This means that the formula for the number of leaves in a 3-1 tree with exactly m vertices is l = 4m - 2 - 3m = m - 2.