Question Let $T=(V,E)$ be a tree with exactly 3 leaves, and $n$ vertices, as $n\ge 5$. Prove the following

Question

Let $T=(V,E)$ be a tree with exactly 3 leaves, and $n$ vertices, as $n\ge 5$. Prove the following:

1. There is exactly one vertex in the tree of the degree $3$.
2. Prove that for every vertex $v\in V$: if $d_{T}(v)\neq 1, 3$, then $d_{T}(v)=2$

My Attempt: 1. I tried to prove that using a contradiction proof: suppose by contradiction that there exists no vertex in the degree of $3$, and then suppose by contradiction that there exists more then 1 vertex with the degree of 3 in $T$.

First, I started with the case for a tree with $5$ vertices.

Given that there are $5$ vertices, then $|V| = |E|-1 \Longrightarrow 6=|E| -1$ such that $|E| = 4$.

By that I conclude that $\sum_{v\in V} d(v) =2|E| = 2\cdot 4 =8$

$d(v_1) +d(v_2)+d(v_3)+d(v_4) +d(v_5) = 8$ There are exactly 3 leaves in the tree ,therefore:

$d(v_1) +d(v_2) +1+1+1 = 8$

$d(v_1) +d(v_2) = 5$

because $v_1, v_2$ can't be leaves, therefore WLOT $d(v_1) =2, d(v_2) =3$,

and we finished.

now, suppose that a tree with $k$ vertices has exactly one vertex in the degree of 3.

Prove that for a tree with $k+1$ vertices (or a tree with $k-1$ vertices) has exactly one vertex in the degree if 3.

Problem is I don't know how to finish the proof from here.

As I said, I wanted to use a contradiction proof, but found myself using induction (I can't see how to not use induction for that argument).

Because I got stuck at the first section, I can't see how I can solve section No.2 as it's based of the first section, As I understand.

Answer 1

Here’s a simpler proof, found by adapting my proof of fact 4 in my first answer. Proof: let $T=(V,E)$ be a tree with exactly three leaves. The sum of the degree of the vertices of T is given by $2|E|=2(|V|-1) =2|V|-2$ There are three vertices of degree 1, so the sum of the degrees for the remaining $|V|-3$ vertices is $2|V|-5$. All vertices must have degree at least 2, which leaves exactly one degree left, meaning exactly one vertex has degree 3, and the remaining vertices all have degree 2.

Answer 2

You’re going to need to use induction, not contradiction. First off, remember that all trees with three or more vertices can be built up from smaller trees by repeatedly appending leaves. So it’s probably helpful to gather some facts about how appending leaves affects the degrees of each vertex, and the total number of leaves in the tree. 1. If you append a leaf to a vertex that was previously a leaf, the old vertex now has degree 2 and is not a leaf anymore, so the number of leaves doesn’t change 2. If you append a leaf to a vertex that had a larger degree before, then you increase the number of leaves by one, and the degree of the original vertex by one. 3. Only if your original vertex had degree zero does appending a leaf change the number of leaves in any other way: this way the number goes up by two since the original vertex now becomes a leaf, but this only occurs if the original graph had only one vertex.

You will need one other fact: 4. If you take a tree with only two leaves, than any other vertices have degree two. This can be seen because the sum of the degrees of all the vertices will have to be $$ 2|E| = 2( |V| -1) = 2|V|-2 $$ After subtracting the two leaves from this vertex total, we get that that the total degree sum for the other $|V|-2$ vertices is $2|V|-4$, and since we know each of these vertices has to have degree at least two, they must all have exactly 2.

Now for the proof, You already showed the base case Now assume that for $k>5$, trees with exactly 3 leaves and k-1 vertices have exactly one vertex of degree, and exactly k-5 vertices of degree 2. let $T$ be a tree with $k (k>5)$ vertices, and exactly 3 leaves. Since all trees have at least two leaves, we may pick a leaf $L$, and define $T’$ to be $T-L$, the graph generated by removing $L$ from $T$. We know by fact 3, that $T’$ will have to have either 2 or 3 leaves.

Now we consider three cases: Case 1: $T’$ has three leaves. In this case since $T’$ Has $k$ vertices, we may use the inductive hypothesis and assume $T’$ Has exactly one vertex of degree 3, and k-5 vertices of degree 2. By fact 1, we know that $L$ must have been attached to one of the three leaves of $T’$, this vertex must then have degree 2 in $T$. Thus in total, we know $T$ has k-4 vertices of degree 2, and the one that still has degree 3 from $T’$

Case 2: $T’$ has 2 leaves. By fact 4, we know that the rest of the vertices must have degree 2, and by fact 2, we know that $L$ must have been attached to one of the non-leaves in $T’$. Since this vertex has degree 2 in $T’$, it must have degree three in $T$.

QED