0

What are the necessary and sufficient conditions for when an collection of non-negative integers $v_1,\ldots,v_k$ are the degrees of the vertices of some undirected graph, and how would one construct such a graph given $v_1,\ldots,v_k$?

vhspdfg
  • 894
  • What have you tried? What theorems do you think are related? How would the answer differ if it were a directed graph? – David G. Stork Oct 02 '19 at 02:05
  • I know that $v_1+\ldots+v_k$ must be even, and obviously none is larger than k. That's all I know. I don't know graph theory.

    I actually want to know for an extremely practical reason—a card exchange in which each person receives as many cards as they send, and each person specifies how many cards they want to sent. I want the graph to preferably be undirected so that every exchange is a swap.

     – vhspdfg Oct 02 '19 at 02:08
  • Thank you saulspatz, this answers it! – vhspdfg Oct 02 '19 at 02:12

0 Answers0