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...
2014-16 Odd and even independent sets, 4.0 out of 5 based on 3 ratings