Eulerian Subgraphs

Problems and Contests
#1

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.
Your task is to count the number of Eulerian subgraphs.

(Link: CSES - Eulerian Subgraphs)

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.

Can anyone help me understand why this will always work?

#2

Any help would be appreciated. TIA.

#3

Hello @ajajaj2807 !! The idea for a single connected component is here https://math.stackexchange.com/questions/2574962/number-of-even-spanning-subgraphs

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}