A graph defined by a set of positive integers

Question

I'm struggling to find a proof for this proposition from chromatic graph theory by bundy.

Let be $S$ a set of positive integers, with maximum element $n$. There exists a graph $G$ on $n+1$ vertices such that:

1. For each vertex $u\in V(G)$, we have that $d(u)\in S$
2. For all $k\in S$ there exists a vertex $v\in V(G)$ such that $d(v)=k$

What I try is using induction in the cardinality of $S = n$, for $n =1$ we have the complete graph, and when $n=2$, we if we have $m_1$, $m_2$ if $m_1$ is less than $m_2$, we can make the complete in $m_1$ vertex and then combine with $m_2- m_1 + 1$ vertex using the product between graphs, but when I try to make the inductive step I get stuck, I try removing $n$, and decrease all elements 1 degree if I have 1 in $S$ it's easy just add the vertex who are going to need since we don't know if the second bigger element is $n - 1$. But if 1 is not in $S$ I don't know how to proceed. Is this the right approach? I would prefer a hint, or a suggestion on another approach

Answer 1

As far as I can tell, it's possible to modify your attempts to work in each case. As requested...

Hints:

1. There's two ways of applying induction: deleting $n$ from $S$, and subtracting $1$ from everything in $S$. They work in different cases.

2. When $n-1 \not\in S$, try replacing $S$ with $S \cup \{n-1\}$.

But for those who don't want hints... we induct on $n=|S|$. Base cases: it's true when $n=1$, realized by $K_2$, and when $n=2$ realized by $K_3$ and $K_3$ minus an edge. Now assume $n \geq 3$.

Case I: $1 \in S$ and $n-1 \in S$.

We apply induction to $S':=\{d-1:d \in S \setminus \{n,1\}\}$. Since $\mathrm{max}(S')=n-2$, we get an $(n-1)$-vertex graph with degree set equal to $S'$, then we (a) add an isolated vertex, and (b) add a vertex and connect it to every other vertex. This gives an $(n+1)$-vertex graph with degree set equal to $S$.

Case II: $1 \in S$ and $n-1 \not\in S$.

We apply induction to $S':=(S \setminus \{n\}) \cup \{n-1\}$. Since $\mathrm{max}(S')=n-1$, we get an $n$-vertex graph with degree set equal to $S'$, and add a pendant edge to the degree-$(n-1)$ vertex (noting that there can only be one, otherwise we contradict $1 \in S'$).

Case III: $1 \not\in S$.

We apply induction to $S':=\{d-1:d \in S\}$. Since $\mathrm{max}(S')=n-1$, we get an $n$-vertex graph with degree set equal to $S'$, then we add a vertex and connect it to every other vertex. This gives an $(n+1)$-vertex graph with degree set equal to $S$ (we end up with $2$ degree-$n$ vertices).

And I note that in all three cases the modified $S$ is non-empty, so has a maximum element.

Answer 2

I can do point 2. Still working on 1.

Let's try to draw $G$ given $S$. The maximum element of element is $n$. It is clear that we can have a vertex in a graph with $n+1$ vertices whose degree is $n$.

The other possible elements in $S$ are $1,2,...,n-1$ since $n$ is the largest element ($S$ may have only some of these).

It is no problem to draw a graph $G$ on $n+1$ vertices whose degrees have a degree among $1,2,3,...,n-2,n-1$ and each of the numbers $1,2,3,...,n-2,n-1$ is the degree of at least one vertex as follows. Label the vertices of $G$ by $v_1,v_2,...,v_n,v_{n+1}$. Give vertex $v_1$ degree $n$ (by making it adjacent to all of $v_2,v_3,...,v_n,v_{n+1}$). Then give vertex $v_2$ degree $n-1$ (by making it adjacent to enough of $v_3,...,v_n,n_{n+1}$, starting from the leftmost vertex in the list, to give $v_2$ degree $n-1$). And so on. Yuu will end up with two vertices of the same degree.

Now, suppose that one of the numbers $1,2,3,...,n-2,n-1$ is not contained in $S$. The graph described above still satisfies the requirement, since all the possible numbers that could be in $S$ (i.e. $1,2,3,...,n-2,n-1$) are the degree of at least one vertex of $G$. So we are done.