2
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ If a graph has an Eulerian path then it must be connected ? ... Are your the graphs labelled or unlabelled ? $\endgroup$ – Donald Splutterwit Jul 28 '17 at 10:44
  • $\begingroup$ @DonaldSplutterwit an Eulerian trail uses every edge, so every edge must be in the same component. This isn't the same as being connected, as you could have isolated vertices. $\endgroup$ – Especially Lime Jul 28 '17 at 10:48
  • $\begingroup$ @EspeciallyLime Of course there might be verticies with valency zero. (They will not be connected) ... Thanks for bringing this to my attention. $\endgroup$ – Donald Splutterwit Jul 28 '17 at 10:53
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you mean what I just added, can you look at what I added please? :D $\endgroup$ – sssss Jul 28 '17 at 11:10
  • $\begingroup$ Why is $a_1=1$? It can either be a graph with $V={a}$ and $E=\emptyset$ or $E={(a,a)}$ so $a_1=2$ you might be mistaken with $b_n$ which there it is 1 but $b_3=1$ because however you do an Eulerian graph with 3 vertices it will allways be the same (each vertex has the same neighbors) and so $b_3=1$. You might be mistaken with what I meant $a_n$ and $b_n$ represents $\endgroup$ – sssss Jul 28 '17 at 14:49
  • $\begingroup$ Because that's not much, you can even write down all the options for n=3. Then you will see $a_3=8$ $\endgroup$ – sssss Jul 28 '17 at 15:08
  • $\begingroup$ Ah, I was assuming simple graphs (where the only possibilities for $n=3$ are the complete graph and the empty graph). If loops and multiple edges are allowed then I understand why your formula is right. $\endgroup$ – Especially Lime Jul 28 '17 at 15:52
  • $\begingroup$ Tought so, but I never said only simple graphs :) $\endgroup$ – sssss Jul 29 '17 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.