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).