0

I was given a bunch of degree sequences and had to determine whether or not a graph was possible.
I used the Handshaking Theorem and concluded there was no graph if the sum of degrees was odd.
However, a lot of the times it summed to an even number but there was no simple graph for the sequence.
All the time there was a non-simple graph, however.
Will there always be a non-simple graph?

Natash1
  • 1,379
  • 1
    There is not always a simple graph (or even a non-simple graph). The Erdős-Gallai theorem describes when a degree sequence is realizable as a graph. – MJD Oct 22 '17 at 15:47
  • Thanks.
    I was wondering when there would be a non-simple graph however. So I wonder why it was marked as duplicate with the corresponding link.     – Natash1 Oct 22 '17 at 23:04

0 Answers0