# Prove that in two trees with same vertices there exists a vertex that the sum of its' degree in both trees is maximum $3$

I came across this question and I tried to give myself a direction but couldn't:

Given $T1 = (V, E_1)$ and $T2 = (V, E_2)$ two trees with same group of vertices. Prove that there is a vertex $v$ such that $deg(v)_{T1} + deg(v)_{T2} \leq 3$.

Now I thought about that in a tree there are at least two leafs, we take one and we show that its' degree in $T2$ is less or equal 2, but that is obviously not a condition and not always correct.

I would be happy for a direction!

• What can you say about the sum of the degrees of the vertices of a tree? – Gerry Myerson May 24 '13 at 9:30
• A tree is connected. therefore the minimum sum of degrees in a tree is $n-1$. A tree has no cycles, therefor each node has a maximum of 2 neighbours, except two that are the leaves, therefore the maximum is $2 * (n-2) +2$. I hope that's correct, but, what does that say? – TheNotMe May 24 '13 at 9:38
• @TheNotMe Note that $\sum_v \mathrm{deg}(v) = 2|E|$ holds for every graph $(V,E)$. What can you say about $|E|$ for a tree ... – martini May 24 '13 at 9:40
• I can say that $\frac{n-1}{2} \leq |E| \leq n-1$ in a tree. And by the way, why the downvote? – TheNotMe May 24 '13 at 9:43
• It is not true that "each node has a maximum of 2 neighbours, except two that are the leaves" as a tree can have lots of vertices of very high degree. But I maintain that there is a formula for the sum of the degrees as a function of $n$. Draw a few trees with different values of $n$, add up the degrees, look for a pattern, try to prove it always holds. – Gerry Myerson May 24 '13 at 10:08

I have solved this afterall. We want to prove that in $G=(V, E_1 \cup E_2)$ there is a vertex $v$ such that $deg(v) \leq 3$. We assume that all the vertices in $G$ are greater than $3$ (at least $4$.) Let $|V| = n$. Then $\sum_{v \in V} {deg(v)} \geq 4n$. Now, $T_1$ and $T_2$ are trees so each one of them has $n-1$ edges, so $|E_1| = |E_2| = n-1$. We know that $|E_1 \cup E_2| \leq |E_1| + |E_2|$ which means $|E_1 \cup E_2| \leq 2n-2$. But the sum of degrees is $\geq 4n$, sp in $E_1 \cup E_2$ there are at least $2n$ edges (coming from the fact that $\sum_{v\in V} {deg(v)} = 2|E|$,) which means that our assumption that all vertices in $G$ have a degree greater than $3$ is wrong. Thus, there exists a vertix $v$ whose degree is less or equal to $3$.