Number Of Maximal-Degree-$k$ Graphs Over $[n]$

Question

Given $n,k\le n\in\bf{N}$, how many graphs are there over the vertex set $\{1,\dots,n\}$ with the property that each vertex is of degree $\le k$?

Answer 1

I don't have a full answer, but there are some easy cases.

• $k=0$: there is one graph, with no edges.
• $k=1$: you've found A000085 already, but I want to comment on the e.g.f. Consider that the only connected graphs where every vertex has degree at most $1$ are the trivial graph on one vertex, and the graph consisting of two vertices and one edge between them. That is, the e.g.f of connected graphs with this property for $k=1$ is $x + \frac12 x^2$. Then the e.g.f. for all labelled graphs with the property is $e^{x + \frac12 x^2}$ by Riddell's formula for labelled graphs. This e.g.f. is mentioned by OEIS.
• $k=2$: the connected graphs where every vertex has degree at most $2$ are the path graphs and the cycle graphs. For $n=1$ and $n=2$ we have the same graphs as with $k=1$; for $n>2$ we have $\frac12 n!$ path graphs (a path joining $n$ labelled vertices is basically a permutation, but we need to divide by two because the vertices in a path can be read forwards or backwards to give two permutations), and $\frac12 (n-1)!$ cycle graphs (similar reasoning). Therefore the e.g.f. of connected labelled graphs is $x + \frac12 x^2 + \sum_{n=3}^\infty \frac{n+1}{2n} x^n$, and the e.g.f. of all labelled graphs is $\exp\left(x + \frac12 x^2 + \frac12 \sum_{n=3}^\infty \frac{n+1}{n} x^n\right)$. This simplifies via standard power series to $\exp\left(\frac12 (\frac{x^3}{1-x} + \ln\frac{1}{1-x} + x + \frac12x^2)\right)$, but I'm not sure whether that is useful.
• $k=n-1$: each edge can be present or not completely independently of the other edges, so there are $2^{\frac12 n(n-1)}$ graphs.

For the other cases, even counting the connected graphs is tricky.