Degree sequences of multigraphs with bounded multiplicity

Question

I got to thinking about this problem while sifting through the math puzzles for dinner thread. There's a fun puzzle by rgrig which asks the guests to prove that when they came to dinner two of them shook hands the same amount of times. The solution is to make the handshake graph, and apply the pigeonhole principle on the vertex degrees. The key observation is that if there are $n$ guests, then the degrees 0 and $n-1$ cannot both occur.

Yaakov Baruch made the astute comment that the result is false if the forgetful mathematicians shake hands twice with each other. However, note that mathematicians are probably not so forgetful to shake hands three times with someone. This leads us to the following questions:

Question 1. Is it true that for large $n$, every loopless multigraph on $n$ vertices with at most two parallel edges between any two vertices has two vertices of the same degree? This is false for $n=3,4,5,6,7$.

Question 2. Is there a nice characterization of such degree sequences?

I'll finish with what is known. If we allow loops, then the problem is trivial, because all sequences whose sum is even are degree sequences. To see this, put a matching on the odd degree vertices, and then add loops. For simple graphs, there are many nice characterizations. For example, the Erdos-Gallai theorem says that a decreasing sequence $(d_1, \dots, d_n)$ is a degree sequence of a simple graph if and only if $\sum_i d_i$ is even and for all $k \in [n]$

\[ \sum_{i=1}^k d_i \leq k(k-1)+ \sum_{i=k+1}^n \min (k, d_i). \]

This sort of answers Question 2, since a degree sequence of a multigraph with multiplicity at most 2 is the sum of two degree sequences of simple graphs. However, this is a rather convoluted characterization, and it is unclear how to answer Question 1 from it.

I'll end by mentioning that if we do not bound the multiplicity of edges, then there is a nice characterization of degree sequences of multigraphs by Hakimi (1962).

Answer 1

The answer to Question 1 is no. Here's a construction. First we construct a simple graph $G_n$ on $n$ vertices for each $n\geqslant3$ which has every degree from $1$ to $n-1$ inclusive occurring, with the degree $n-1$ occurring only once. You do this recursively: to construct $G_n$, just take the complement of $G_{n-1}$ and add a vertex joined to all the others.

Now to construct the desired multigraph: label the vertices of $G_n$ as $v_1,\dots,v_n$ in such a way that the degrees of these vertices are increasing; then these degrees are $1,2,\dots,i,i,i+1,\dots,n-1$ for some $i < n-1$. Now just duplicate the edge from $v_j$ to $v_n$ for $j=i+1,\dots,n-1$, and you have your multigraph with distinct degrees $1,2,\dots,n-1,2n-i-2$.

Answer 2

Here is the answer of Question 2: (Fulkerson,Hoffman,McAndrew[1965]) A decreasing sequence $(d_1,d_2,...,d_n)$ of non-negative integers is a degree sequence of a loopless multiple graph with each edge capacity atmost 2 if and only if $ \sum_{i=1}^{n} d_i$ is even and for each subset A of [n] $$ \sum_{i=1}^{n} min(d_i,2|A-\{i\}|) \geq \sum_{j \in A} d_j$$