Daily Archives: September 19, 2014

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}.\]

GD Star Rating
loading...