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,2,2,3
- 0,1,2,3
- 2,2,2,2
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.
Copyright © 2021 JogjaFile Inc.
They're all realizable for multigraphs; with 4 vertices, you can just try by hand:
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).