How many Eulerian graphs with $n$ vertices such that $\forall v\in V:d(v)<4$ are there? (Note the graph doesn't have to be connected.)
I can't manage to find an answer. The closest I got was $2^{n}$ but that's right only for $n\leq 3$.
Any ideas?
So I keep tried and thought of that:
Let $b_n$ be the number of connected Eulerian graphs with n vertices. $b_n=1$ for $n\leq 3$ and $b_n=(n-1)b_{n-1}$ for $n\geq 4$.
Let $a_n$ be the number of Eulerian graphs with n vertices (the number we want to find). $a_n=\sum_{i=0}^n{n\choose i}b_i$
The reason is that we choose $i$ vertices to be the vertices that are connected (you can say "part of the real graph" because the others don't matter, the Euler path isn't passing through them) and then we multiply it by the number of Euler cycles we can build from them. So we get a sum of ${n\choose i}\cdot b_i$
It's pretty easy to see $b_n$ is like the factorial sequence with a little change. We will get $b_n=\frac{(n-1)!}{2!}$ for $n\geq 4$
And so we got $a_n=2^n$ for $n\leq 3$ and $a_n=\sum_{i=0}^3{n\choose i}+\sum_{i=4}^n {n\choose i}\frac{(i-1)!}{2!}$ for $n\geq 4$
Is that correct?
If it is, is there any way to get rid of the $\sum$?
If a graph is Eulerian then $d(v)$ has to be even for every $v$. If $d(v)<4$ then there are only two options: $0$ and $2$.
If every vertex has degree $0$ or $2$ then the graph is a union of cycles and isolated vertices.
So, which graphs of this form are actually Eulerian? Can you count the ones that are?
[edit] What you've added is (I now realise) correct for multigraphs. I got $$a_n=1+\sum_{i=3}^n\binom ni\frac{(i-1)!}{2},$$ but I was assuming simple graphs.
I can't see how to avoid the sum.