Prove that there exists a $k$ such that the sequence obtained by listing each element of $S$ a total $k$ times is a degree sequence of some graph.

Question

I'm currently working in the following graph theory excercise:

Let $S = \{2, 6, 7\}$. Prove that there exists a positive integer $k$ such that the sequence obtained by listing each element of $S$ a total $k$ times is a degree sequence of some graph. What is the minimum value of $k$?

I'm basing on the theorem:

But haven't find a way to suit the lemma in my solution, thanks in advance for any hint or help.

Answer 1

Vertex of the degree $7$ has $7$ neighbour, so $k\geq 3$.

Case $k=3$ is impossible by handshakeing lemma.

Now try $k=4$:

$$2,2,2,2,6,6,6,6,7,7,7,7$$

Say first vertex with degree 7 is not connected with the 2 degree vertices, then,

$$2,2,2,2,5,5,5,5,6,6,6$$

and first vertex with degree 6 is not connected with the 2 degree vertices, then,

$$2,2,2,2,4,4,4,4,5,5$$

and first vertex with degree 5 is not connected with the 2 degree vertices, then,

$$2,2,2,2,3,3,3,3,4$$

and vertex with degree 4 is not connected with the 2 degree vertices, then,

$$2,2,2,2,2,2,2,2$$

And with them we make a 8-cycle

Answer 2

This is a partial answer which addresses only the first part of the question: proving the existence of $k$, without trying to determine the minimal value.

Given any set $S=\{s_1,s_2,\dots,s_n\}$ of $n$ positive integers, let $k$ be the least common multiple of the numbers $s_1+1,s_2+1,\dots,s_n+1$. Then the graph $G=\frac k{s_1+1}\cdot K_{s_1+1}+\frac k{s_2+1}\cdot K_{s_2+1}+\cdots+\frac k{s_n+1}\cdot K_{s_n+1}$ has $k$ vertices of degree $s_i$ for each $i$.

For the given set $S=\{2,6,7\}$ this dumb construction uses $k=42$, which is far from the minimum, as we can see from the accepted answer.