Prove that the number of simple Eulerian graphs with vertex set $\{1, 2, \dots, n\}$ is $2^{\binom{n-1}{2}}$.

Solution

1. I will define two sets of graphs:

• $G_{n-1}$: The set of simple graphs with vertex set ${1,2,\dots,n-1}$.
• $E_n$: The set of Eulerian graphs with vertex set ${1,2,\dots,n}$.

2. I will show that the sizes of these two sets are the same by establishing a bijection between $G_{n-1}$ and $E_n$.

3. Check Injectivity:

• i. Given $G \in G_{n-1}$, construct a graph $E \in E_n$ by adding the $n$-th vertex to $G \in G_{n-1}$.
• ii. Since Eulerian graphs have no odd degree vertices, in $E$, all vertices must have even degrees.
• iii. Consider each odd-degree vertex in $G$, and connect it to the $n$-th vertex. Then these vertices become even-degree vertices. At this point, it is clear that the $n$-th vertex also becomes an even-degree vertex.
  This is because the sum of the degrees of all vertices in a graph is even ,since it equals twice the number of edges. If the degree of the $n$-th vertex were odd, then the sum of all vertex degrees would be odd, which is a contradiction.
• iv. Thus, $E$ is uniquely determined, and the construction is injective.

4. Check Surjectivity:

• i. Let's check that for every $E \in E_n$, there is a corresponding graph $G \in G_{n-1}$.
• ii. Delete the $n$-th vertex from $E$. Since $E$ is a simple Eulerian graph, the remaining graph is simple with vertex set ${1,2,\dots,n-1}$, which belongs to $G_{n-1}$.

5. Therefore, this mapping is bijective.

6. The number of elements in $G_{n-1}$ is $2^{\binom{n-1}{2}}$.

• This is because there are $\binom{n-1}{2}$ possible edges between $n-1$ vertices, and for each edge, we can either include or not include it.

7. Since the mapping is bijective, the size of $E_n$ is also $2^{\binom{n-1}{2}}$.