Check if graph is multigraph given degree sequence

387 Views Asked by At

I am given some degree sequences of graphs, and my question is what is the method to determine which of them are sequences corresponding to multigraphs.

  1. 1,2,2,3
  2. 0,1,2,3
  3. 2,2,2,2
1

There are 1 best solutions below

0
On

They're all realizable for multigraphs; with 4 vertices, you can just try by hand:

enter image description here

We also see that $(1,2,2,3)$ and $(2,2,2,2)$ are realizable for simple graphs.

However, the sequence $(3,2,1,0)$ is not realizable for simple graphs: the vertex of degree 3 needs to attach to 3 other vertices, but there are only 3 other vertices and one has degree 0 (i.e., no edges).