Circulant graphs can be used to realize the $\lfloor n\Delta/2 \rfloor$ bound in a large number of cases, and in the other cases, we can modify them slightly to achieve this bound.
- When $n$ is even and $\Delta$ is even (so $\Delta \leq n-2$), we pick a set of distances comprising $\Delta/2$ distances in $\{1,2,\ldots,n/2-1\}$.
For example, when $n=10$ and $\Delta=6$, we can take the distances $\{1,2,3\}$, which gives:
- When $n$ is even and $\Delta$ is odd, we pick a set of distances comprising $(\Delta-1)/2$ distances in $\{1,2,\ldots,n/2-1\}$ and $n/2$.
For example, when $n=10$ and $\Delta=5$, we can take the distances $\{1,2,5\}$, which gives:
- When $n$ is odd and $\Delta$ is even we pick a set of distances comprising $\Delta/2$ distances in $\{1,2,\ldots,(n-1)/2\}$.
For example, when $n=11$ and $\Delta=6$, we can take the distances $\{2,3,4\}$, which gives:
Finally, when $n$ is odd and $\Delta$ is odd (so $\Delta \leq n-2$), $n\Delta/2$ is not an integer, so we can't achieve the maximum with circulant graphs. The best we could possibly do is $\lfloor n\Delta/2 \rfloor$. To achieve this:
We take a $(\Delta-1)$-regular graph as above, but do not take distance $1$ edges (we need to take at most $(\Delta-1)/2 \leq (n-3)/2$ distances, so this is possible).
We observe that the edges of distance $1$ form a Hamilton cycle in the complement of the graph. We pick $(n-1)/2$ disjoint edges from this Hamilton cycle (i.e., no two edges share an endpoint), and add them to our construction.
For example, when $n=11$ and $\Delta=7$, we can take the above $6$-regular graph and add in edges around the outside as follows:
This gives $\lfloor n\Delta/2 \rfloor$ edges in every case (as expected).
You’re right: you cannot have a vertex of degree $5$ when there are only $4$ other vertices of positive degree. You’ve proved that $1,1,2,3,5,5,6,7$ is not a possible degree sequence of a simple graph.
Nothing is wrong: the handshaking lemma is a necessary condition, but not a sufficient one.
Best Answer
Let $G$ have $n$ vertices each with degree $d$. Then the sum of all degrees is twice the number of edges, i.e.$$nd=44$$Now we are interested in natural number solutions for the above equation which may represent a simple graph, assuming you want simple $G$.
For example, $n=1,d=44$ is not a feasible solution since it represents a single vertex with $22$ self-loops. You may recall that in a simple regular graph of $n$ vertices, the maximum degree of the vertices can be $n-1$; i.e.$$d<n\implies nd=44<n^2\implies n\ge7$$This narrows-down the search. The solutions are $n=11,d=4$ and $n=22,d=2$ and $n=44,d=1$.