# Discrete Math Graph Theory

A sequence $( d_1, d_2,...,d_p)$ is said to be graphic if and only if it is the degree sequence of some simple graph with p vertices. Show that the sequences $(7,5,5,5,3,2,1)$ and $(6,6,5,4,2,2,1)$ are not graphic. So for the first one 7 can't work because there are only 6 other vertices to connect to. But what if you have one degree of multiplicity 2? Then 7 works and I don't think this is what the question is looking for as an answer anyways. Using graph theory in Discrete Math, how would you solve this?

• In a graph with multiple edges, 7 5 5 5 3 2 1 is possible. Also, simple graph. – Karolis Juodelė Mar 19 '14 at 6:46
• I think your nitpick is silly. From the linked article "Unless stated otherwise, the unqualified term "graph" usually refers to a simple graph. A simple graph with multiple edges is sometimes called a multigraph (Skiena 1990, p. 89)." – Stella Biderman Mar 19 '14 at 7:19
• It's also possible to construct a multigraph with degree sequence (6,6,5,4,2,2,1), but I think as others have said, the assumption is that the graphs should be simple. – Perry Elliott-Iverson Mar 19 '14 at 16:14

For the second, two $6$s means that every vertex must has at least two neighbors, since both $6$s connect to every other vertex. But then you can't have a $1$ in the sequence.