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?