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
medges. 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?