# Eulerian Subgraphs

Hello everyone!
I was trying to solve the ‘Eulerian Subgraph’ problem from the CSES Advanced Techniques section. The problem statement looks like this-

You are given an undirected graph that has `n` nodes and `m` edges. We consider subgraphs that have all nodes of the original graph and some of its edges. A subgraph is called Eulerian if each node has even degree.

After being stuck on it for the past three days, I searched on the web and found out the answer is rather a simple expression. It turns out the answer is `pow(m-n+cc, 2)`, where `m` is the number of edges, `n` is total number of nodes, and cc is the number of connected components. But I am not sure how this expression gives us the required result. I wasthinking in the direction of MSTs but could not proceed to prove it.
After that, you can multiply number of solutions for each connected component (since their subgraphs are clearly disjoint), considering that the i-th component has `n_i` nodes and `m_i`, then:
`ans = 2^{n_1 - m_1 + 1} * ... * 2^{n_cc - m_cc + 1} = 2^{sum(n_i) - sum(m_i) + cc} = 2^{n-m+cc}`