Even Subgraphs - Math Problems

Start with what's free, and what's forced

The empty subset always works: if

S = \emptyset

, every vertex has degree

0

, which is even. So the answer is at least

1

Now weigh the two forces against each other:

Each of the

m

edges is either in

S

or out. That is

2^m

raw choices.

Each of the

n

vertices imposes one parity constraint: its degree in

S

must be even.

If those

n

constraints were independent, you would expect

2^{m-n}

valid subsets. The answer is

2^{m-n+1}

, exactly twice that.

So one constraint must be redundant. Ask yourself: across the whole graph, what is always true about the sum of all vertex degrees?

The sum of all degrees is $2|S|$ , always even. So once $n-1$ vertices are even, the last one is even with no choice. One constraint comes for free.

Start with what's free, and what's forced

The empty subset always works: if $S = \emptyset$ , every vertex has degree $0$ , which is even. So the answer is at least $1$ .

Now weigh the two forces against each other:

Each of the $m$ edges is either in $S$ or out. That is $2^m$ raw choices.
Each of the $n$ vertices imposes one parity constraint: its degree in $S$ must be even.

If those $n$ constraints were independent, you would expect $2^{m-n}$ valid subsets. The answer is $2^{m-n+1}$ , exactly twice that.

So one constraint must be redundant. Ask yourself: across the whole graph, what is always true about the sum of all vertex degrees?

The sum of all degrees is $2|S|$ , always even. So once $n-1$ vertices are even, the last one is even with no choice. One constraint comes for free.