How to approach this discrete graph question about Trees. A tree contains exactly one vertex of deg

Landyn Jimenez

Landyn Jimenez

Answered question

2022-05-23

How to approach this discrete graph question about Trees.
A tree contains exactly one vertex of degree d, for each d { 3 , 9 , 10 , 11 , 12 }.
Every other vertex has degrees 1 and 2. How many vertices have degree 1?
I've only tried manually drawing this tree and trying to figure it out that way, however this makes the drawing far too big to complete , I'm sure there are more efficient methods of finding the solution.
Could someone please point me in the right direction!

Answer & Explanation

Fahrleine9m

Fahrleine9m

Beginner2022-05-24Added 11 answers

Step 1
Let n d be the number of nodes of degree d, and let n be the total number of nodes. Then d n d = n and d d n d = 2 ( n 1 ), so
d ( d 2 ) n d = 2 ,
equivalently, n 1 = 2 + d 3 ( d 2 ) n d ..
Step 2
Now substitute the known values n d = 1 for d { 3 , 9 , 10 , 11 , 12 } and n d = 0 for d > 3 otherwise, yielding
n 1 = 2 + ( 3 2 ) n 3 + ( 9 2 ) n 9 + ( 10 2 ) n 10 + ( 11 2 ) n 11 + ( 12 2 ) n 12 = 2 + 1 + 7 + 8 + 9 + 10 = 37.
Kellen Perkins

Kellen Perkins

Beginner2022-05-25Added 3 answers

Explanation:
Suppose there are n 1 vertices of degree 1 and n 2 vertices of degree 2.
- How many vertices are there total?
- If the graph is a tree, how many edges should it have?
- What is the sum of the degrees?

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?