0
$\begingroup$

Is there a tree with seven vertices:
a) With five vertices having degree 1 and two vertices having degree 2? b) With vertices having degrees 2,2,2,3,1,1,1?

So I believe the degree is the number of children vertices there are from the vertex? For a) I believe the answer is yes because I was able to draw a tree as such but for b) I believe the answer is no because I could not conceptualize a tree like this.

I may be taking the wrong definition of degree though or might be thinking about "rooted" trees only. Thank you for any help clarifying this concept and if there is a formula/ theorem for this.

|cite|improve this question
$\endgroup$
  • 6
    $\begingroup$ Recheck your answer to (a)... $\endgroup$ – Casteels Mar 8 '18 at 19:41
  • $\begingroup$ Do you know the handshaking lemma? $\endgroup$ – Kevin Long Mar 8 '18 at 19:53
1
$\begingroup$

HINT

Since every edge will connect exactly two vertices, every edge you add to a graph will increase the sum total of all degrees of all vertices in the graph by $2$. So ... the sum total should always be what kind of number?

So, count a little harder for whatever you drew for a) ...

Also, try a little harder for b) ...

|cite|improve this answer
$\endgroup$
1
$\begingroup$

For (b) start drawing from the vertices of degree 1, since the look of the graph at those vertices is unique.

You can probably get to this example:

.-.-.-.-.<:

|cite|improve this answer
$\endgroup$

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.