0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ In a graph with multiple edges, 7 5 5 5 3 2 1 is possible. Also, simple graph. $\endgroup$ – Karolis Juodelė Mar 19 '14 at 6:46
  • $\begingroup$ 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)." $\endgroup$ – Stella Biderman Mar 19 '14 at 7:19
  • $\begingroup$ 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. $\endgroup$ – Perry Elliott-Iverson Mar 19 '14 at 16:14
2
$\begingroup$

I think you're arguement for the first one holds. Usually in these kinds of problems graphs don't have two edges connecting the same vertices.

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.

$\endgroup$
0
$\begingroup$

It is impossible to draw this graph. A simple graph has no parallel edges nor any loops. There are only 7 vertices in first sequence, so each vertex can only be joined to at most six other vertices, so the maximum degree of any vertex would be 6. Hence, you can’t have a vertex of degree 7

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.