Given $T(n,m)$ which contains only vertices of degree 1 and 3. How many vertices are of degree 1? Is it similar to compute in thi link? How many vertices of degree 1 in a tree? Thank you.
Asked
Active
Viewed 869 times
0
-
1What does $T(n,m)$ denote? I assume a Tree, but what are $n$ and $m$ supposed to represent? – Justin Benfield Mar 12 '16 at 15:35
-
@JustinBenfield. $T(n,m)$ means tree with vertices $n$ and degrees $m$. – Bayoy Mar 12 '16 at 15:37
-
1Degree meaning...highest degree of a vertex? – Justin Benfield Mar 12 '16 at 15:41
-
@JustinBenfield. Yes Sir.. – Bayoy Mar 12 '16 at 15:48
-
A tree with only vertices of degree one and three is similar to a complete binary tree except that the root has three children instead of two. All other branching points have either two children or zero children. Similar questions have been asked with respect to complete binary trees in the past. Try looking at answers to questions like those and see if you can modify the result to account for the extra degree on the root. – JMoravitz Mar 12 '16 at 15:50
2 Answers
0
As a base case, the Claw graph is a minimal example, and it has three $\deg 1$ vertices (it is an example of $T(4,3)$). Each time we add a new interior vertex from here, we must increase the count of $\deg 1$ vertices by 1, but the total vertex count goes up by 2, hence we see that a tree of this type must have exactly $2k$ total vertices for some $k>1$, and $\frac{n}{2}+1$ degree 1 vertices.
Justin Benfield
- 3,992
-
-
Degree is fixed at 3 for interior vertices. I think I messed up the formula, but the idea is right. – Justin Benfield Mar 12 '16 at 16:02
-
0
Taking the first answer in the linked question here as a basis, you can imagine your graph describing a single elimination tournament where the final match is instead a 3 person free-for-all instead of the usual one-on-one matches.
For $n$ players, to eliminate $n-3$ of them there will be $n-3$ games played one-on-one, and then one more game for the final match free-for-all.
Such a graph will have $2n-2$ vertices. One can argue via contrapositive that if it had a different number of vertices it would necessarily have a different number of leaves.
Rewording such that the total number of vertices is $n$ then, we have $\frac{n+2}{2}$ vertices of degree one.
(note: having an odd number of vertices total is not allowed by the handshaking lemma)
