Existence of a multigraph

Question

I'm an undergraduate student majoring in mathematics. I'm solving my home assignment and got stuck at this problem.

Suppose $d_1\geq d_2\geq\dots \geq d_n\geq 1$ and $\sum_{i=1}^nd_i$ is even. Prove that there is a multigraph with degree sequence $d_1, d_2, > \dots, d_n$ if and only if $d_1 \leq \sum_{i=2}^nd_i$.

So, please help me.

Answer 1

Necessity. The sum $\sum_{i=1}^nd_i$ is always even because each edge connects two vertices and therefore it is counted twice. As there are no loops the each degree should be less equal to the sum of the others.

Sufficiency. Show by induction with respect to $d_1$ that if $d_1\geq d_2\geq\dots \geq d_n\geq 1$ and $\sum_{i=1}^nd_i$ is even then there is a multigraph with degree sequence $d_1,d_2,\dots,d_n$.

Hint for the inductive step.

1) Assume first that $d_n\geq 2$.

1.1) If $n$ is even then, by the inductive hypothesis, there is a multigraph with degree sequence $d_1-1,d_2-1,\dots,d_{n}-1$.

1.2) If $n$ is odd then, then $\sum_{i=1}^nd_i$ is even implies that there is a minimal index $j$ such that $d_j$ is odd. Then $d_j\geq 3$, and by the inductive hypothesis, there is a multigraph with degree sequence $d_1-1,d_2-1,\dots, d_j-2,\dots,d_{n}-1$.

2) Otherwise $d_n=1$. Let $k\leq n$ be such that $d_{k+1}>d_k=1$.

2.1) If $k$ is even then, by the inductive hypothesis, there is a multigraph with degree sequence $d_1-1,d_2-1,\dots,d_{k+1}-1$.

2.2) If $k$ is odd then $\sum_{i=1}^n d_i$ is even implies that there is a minimal index $j$ such that $j>k$ and $d_j$ is odd. By the inductive hypothesis, there is a multigraph with degree sequence $d_1-1,d_2-1,\dots, d_j-2,\dots,d_{k+1}-1$.

Answer 2

An alternative construction (that doesn't use induction):

First observe that if $d_1 = \sum_{i=2}^n d_i$, we can form a multigraph with degree sequence $d_1, \dots, d_n$ by simply adding $d_i$ edges between $v_1$ and $v_i$ for each $i \in \{2,\dots, n\}$.

In general, of course, $d_1$ may be less than $\sum_{i=2}^n d_i$, but we can always reduce to the special case above if we can somehow add $k \equiv \frac{1}{2}(\sum_{i=2}^n d_i - d_1)$ edges between vertices in $\{v_2,\dots, v_n\}$ (to make up for the difference between $d_1$ and $\sum_{i=2}^n d_i$. Note that $\sum_{i=2}^n d_i - d_1 = \sum_{i=1}^n d_i - 2d_1$ is even, since $\sum_{i=1}^n d_i$ is even by assumption. Note also that $k \leq \frac{1}{2}(\sum_{i=2}^n d_i - d_2) = \frac{1}{2}\sum_{i=3}d_i$ since $d_1 \geq d_2$.

To add the $k$ edges between vertices in $\{v_2,\dots, v_n\}$, consider adding edges between $v_i$ and $v_{i-1}$, starting with $i = n$, until $d_i$ has been "depleted." That is, add $d_n$ edges between $v_n$ and $v_{n-1}$, $d_{n-1} - d_n$ edges between $v_{n-1}$ and $v_{n-2}$, $d_{n-2} - (d_{n-1} - d_n)$ edges between $v_{n-2}$ and $v_{n-3}$, and so on, finally adding edges between $v_3$ and $v_2$ until no more edges can be added to $v_3$. This is possible because $v_2 \geq v_3 \geq \dots \geq v_n$, so we can clearly add $\leq d_i$ edges between $v_i$ and $v_{i-1}$. Moreover, at least $\frac{1}{2}\sum_{i=3}d_i$ edges are added in total, since we've depleted degrees $d_3,\dots, d_n$. Therefore, from the $k \leq \sum_{i=3}^n d_i$ bound above, we see that we can add the $k$ edges this way.