728x90
반응형
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}}$.
728x90
반응형