Find $n$ in Tree given...

Question

Be T tree order n given:

$(a)$ $ 95 < n < 100$

$(b)$ Just have vertices with degree 1,3,5

$(c)$ T has twice the vertices of degree 3 that degree 5

$n$ is...?

Okay, i think that can use handshake to sum degree to obtain $2e$ and solve for algebra, but I don't see how propose equation. Hope that can help me with it

Answer 1

Let $v_1$, $v_3$, and $v_5$, represent the number of vertices with degree 1, 3, and 5 respectively. Since $T$ is a tree, you know there are $n-1$ edges. Therefore, you know that $$v_1+v_3+v_5=n\\v_1+3v_3+5v_5=2(n-1)$$ Substituting in that $v_3=2v_5$, we get $$v_1+3v_3=n\\v_1+13v_3=2n-2$$ Subtracting the first equation from the second gives $10v_3=n-2$. Since $95<n<100$ and $n-2$ is a multiple of 10, we conclude that $n=98$.

Answer 2

The relevant equations are

$$ |V| = |E| + 1. $$

$$ \sum_{v \in V} \deg(v) = 2|E|. $$

$$ \#(\text{leaf vertices}) = 2 + \#(\text{degree 3 vertices}) + 2\#(\text{degree 4 vertices})+3\#(\text{degree 5 vertices}) + \cdots $$