graph theory: upper bound on edge number, given number of vertices and thanks for letting me become a member.
I have a rather basic question on graph theory.
Suppose G is a finite graph, without loops, multiple edges or directed edges.
Let n be the number of vertices, let $\Delta$ be the maximum degree.
Find an upper bound on the number of edges in the graph.
(Note that I am not assuming anything about the diameter).
Is there a symbol for this, or any literature on the web or in books?
Are there any tables on the web for small n and small $\Delta$?
This could be seen as a problem in extremal graph theory, but here the forbidden subgraph is simply a star on $\Delta+2$ vertices.
A very naive upper bound is simply $n\Delta/2$, but that bound can only be attained by regular graphs, and if n and $\Delta$ are both odd, then the bound is not an integer and thus certainly not attained.
Many thanks!
 A: 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).
