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!

  • 3
    $\begingroup$ What can you say about the sum of the degrees of the vertices of a tree? $\endgroup$ – Gerry Myerson May 24 '13 at 9:30
  • $\begingroup$ 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? $\endgroup$ – TheNotMe May 24 '13 at 9:38
  • $\begingroup$ @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 ... $\endgroup$ – martini May 24 '13 at 9:40
  • $\begingroup$ I can say that $\frac{n-1}{2} \leq |E| \leq n-1$ in a tree. And by the way, why the downvote? $\endgroup$ – TheNotMe May 24 '13 at 9:43
  • $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.