Construction of graph with degrees $d$ and $(d + 1)$

Question

Let $n = a + b$ and $d$ be non-negative integers such that: $ad + b(d + 1)$ is even and $(d + 1) \leq (n - 1)$. Does there exist a graph with $n$ vertices such that $a$ of them have degree $d$ and $b$ of them have degree $(d + 1)$? Is there an explicit construction?

Answer 1

We start with $k$-regular graphs on $n$ vertices constructed as follows. Put the $n$ vertices around a circle. If $k$ is even, connect each vertex to its $k$ closest neighbours. If $k$ is odd, then $n$ is even, so we can construct a $(k - 1)$-regular graph as before, and then add an edge between each vertex and its antipode.

From this construction the one I was asking for follows. One has to proceed by cases, and I have checked all the details and it works, but I won't write everything here. The idea is that you either construct a $d$-regular graph, then check that you have a large enough matching in the complement, and add part of it to augment the degree of some vertices by 1; or you construct a $(d + 1)$-regular graph, then check you have a large enough matching, and eliminate part of it to decrease the degree of some vertices by 1. It's a bit tedious to check everything but it's quite straightforward.

Answer 2

This is not the answer but maybe that can give some idea:

Fix an integer $k\geq3$. There exist a $(2k-1)$-vertex $(k-2)$-edge-connected simple graph $H_k=(V_k,E_k)$ with $V_k=\{y_1,y_2,...,y_{k+1},z_{1},z_{2},...,z_{k-2}\}$, where all vertices $y_i$ have degree $k$ and all vertices $z_j$ have degree $(k-1)$.

proof: Start with a k-vertex complete graph on the vertices $\{y_1,...,y_k\}$, plus a $(k-2)$-vertex complete graph on the vertices $\{z_1,...,z_{k-2}\}$. Next place an edge from the vertex $y_{k+1}$ to the vertices $y_{k-1}$ and $y_{k}$, then $(k-2)$ edges of the form $y_jz_j$ and $(k-2)$ edges of the form $y_{k+1}z_j$.