3
$\begingroup$

Does there exist a simple graph with five vertices of the following degrees?

(a) 3,3,3,3,2

I know that the answer is no, however I do not know how to explain this.

(b) 1,2,3,4,3

No, as the sum of the degrees of an undirected graph is even.

(c) 1,2,3,4,4

Again, I believe the answer is no however I don't know the rule to explain why.

(d) 2,2,2,1,1

Same as above.

What method should I use to work out whether a graph is simple, given the number of vertices and the degree sequence?

  • 0
    The answer to a, and for d are in fact yes.2011-04-05
  • 0
    Why, for example, do you believe that 2,2,2,1,1 is not possible? Simple sketching should show that it is possible, in more than one way.2011-04-05
  • 0
    @yaakov How do I know this? Is there a given property that tells me this?2011-04-05
  • 0
    not as far as I know. I just took a pen and paper, and searched naively.2011-04-05

5 Answers 5