If $G$ be a Tree with degree $(5,r,s,1,1,1,1,1) $. (I wrote degree in non-increasing order). why all of this condition is True sometimes (I means on some condition)? I try to find an example that includes all following condition. any friends could help me?
1) $G$ has a vertex of degree 2.
2) $G$ has a vertex of degree 3.
3) there is two vertices in $G$ that distance between them is 3.
4) there is two vertices in $G$ that distance between them is 4.
Thanks.
On
By definition, a graph with degree sequence $(5,r,s,1,1,1,1,1)$ has $8$ vertices. We also know that a tree with $n$ vertices has exactly $n-1$ edges. So any tree with this degree sequence has $7$ edges.
By the Handshaking Lemma, we must have $$5+r+s+1+1+1+1+1=2 \times 7=14.$$ I.e., $r+s=4$.
This is sufficient to exclude all possibilities except $(r,s) \in \{(3,1),(2,2)\}$, which are realizable degree sequences. Up to isomorphism, these are the graphs (with their vertices marked by their degrees):
and
The first of the three trees has no vertex of degree 2, and all distances are at most 3, which means 1. and 4. are not true in general.
The second and third have no vertices of degree 3, so 2. is not true in general.
This also means that all four conditions can not be simultaneously satisfied.
But 3. is true in general for these trees.
Hint: The easiest way to this would be to simply draw trees that satisfy these conditions. You should be able to draw a tree that has degree sequence (5,2,2,1,1,1,1,1), which satisfies (1), (3), and (4), and another tree with degree sequence (5,3,1,1,1,1,1,1) that satisfies (2).