Solution: 2014-16 Odd and even independent sets

For a (simple) graph $$G$$, let $$o(G)$$ be the number of odd-sized sets of pairwise non-adjacent vertices and let $$e(G)$$ be the number of even-sized sets of pairwise non-adjacent vertices. Prove that if we can delete $$k$$ vertices from $$G$$ to destroy every cycle, then $| o(G)-e(G)|\le 2^{k}.$

The best solution was submitted by Minjae Park (박민재, 수리과학과 2011학번). Congratulations!

Here is his solution.

An alternative solution was submitted by 김경석 (+3, 경기과학고 3학년). One incorrect solution was received (BHJ).

GD Star Rating