Counting "double bonds" in graphs Here's an interesting puzzle I've set myself. Consider the set of multigraphs (or, if you prefer, graphs with edges weighted by positive integers), excluding graphs with cycles of length 1. Let the degree of a vertex be the number of edges connected to it. (Or if you prefer weighted graphs, the sum of the weights on the edges connected to it.) Let the signature of a graph be the multiset containing the number of degrees of each of its vertices. For example, consider the following multigraph:

It has signature $\{4, 4, 1, 1\}$, since two of its nodes are connected to four edges and two to one edge. (Note that this graph is reminiscent of an acetylene molecule, with its signature corresponding to its chemical formula, $\mathrm{H_2C_2}$. This chemical analogy is the motivation for the question.) Note that the total number of edges in a multigraph is equal to half the sum of the elements of its signature.
I'm interested in the number of multiple edges (double bonds, triple bonds etc.) in a given graph. That is, the number of pairs of vertices that are connected by more than one edge. For the signature $\{4, 4, 1, 1\}$ there is always a multiple edge, because the only graph with that signature is the one above. On the other hand, $\{3,1,1,1\}$ (an ammonia-like graph) only has single bonds. 
Some signatures correspond to more than one graph ("isomers" in chemistry terminology) - for example, $\{4, 4, 4, 1, 1, 1, 1, 1, 1\}$ may have either two double edges or one triple one. Some, such as $\{2, 1\}$ do not correspond to any graph.
My questions are as follows:


*

*given a multiset of integers, what are the necessary and sufficient conditions for it to be the signature of a multigraph?

*given a signature, is there a way to tell whether its corresponding graphs have multiple bonds, short of enumerating all graphs with that signature? 

*what can be deduced about the number of multiple edges in a graph from its signature alone, short of enumerating all graphs with that signature?

*is there a graph with no multiple edge that shares a signature with a graph with at least one multiple edge?
 A: Your 'multiset of integers' or signature is generally called 'degree sequence'.
Your question is about graphs and multigraphs realizing certain degree sequences.
Quite a lot has been researched and written about this.
Ad 1: A necessary and sufficient condition is that the sum of all entries is even (@Henry's comment made me realize that this is only correct when loops are allowed as well, when no loops are allowed his answer is the correct one).
Ad 4: Certainly, lots of them. A very simple one is $(2,2,2,2)$ which is realized
by a 4-cycle, but also by 2 thick edges. Or $(3,3,3,3)$ which is realized by
a complete graph $K_4$, but also by a 4-cycle with 2 thick edges.
For realizing a "simple graph", i.e. one without loops and multi-edges one of
the most famous criteria is the Havel-Hakimi condition (see e.g. https://en.wikipedia.org/wiki/Havel%E2%80%93Hakimi_algorithm).
This brings us to
Ad 2: In view of Ad 4, the signatures that have only realizations with
multiple bonds are those that do not satisfy the Havel-Hakimi condition, but that do satisfy the condition Ad 1.
Signatures that satisfy the Havel-Hakimi condition will often
have both simple realizations and multigraph realizations.
Ad 3: Again, in view of Ad 4, you cannot expect to find a well-defined number.
The best you can tell (without imposing any other constraints) is, that when the sum of the degrees exceeds $2\binom n2$,
where $n$ is the number of entries/vertices, the number of multiple edges is
at least half of the excess.
