The ODD EVEN DELTA problem Let $G = ( V, E )$ be a graph. Let $k \leq |V|$ be an integer. Let $O_k$ be the number of edge induced subgraphs of $G$ having $k$ vertices and an odd number of edges. Let $E_k$ be the number of edge induced subgraphs of $G$ having $k$ vertices and an even number of edges. Let $\Delta_k = O_k - E_k$. The ODD EVEN DELTA problem consists in computing $\Delta_k$, given $G$ and $k$.


  Questions  
  
  
  Is it possible to compute $\Delta_k$ in polynomial time? Which is the best known algorithm to compute it?
  What if $G$ is 3-regular?
  What if $G$ is 3-regular bipartite?
  What if $G$ is 3-regular bipartite planar?
The ODD EVEN DELTA problem is #P-hard, even on 3-regular bipartite planar graphs.

Let $\mathcal{C}$ be the set of vertex covers of a general graph $G$. Then, assuming $G$ has no isolated vertices, the following equation holds (refer to the above article for the proof):

$$|\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^{|V|} \Delta_k \cdot 2^{|V|-k}$$

Counting vertex covers is #P-complete even on 3-regular bipartite planar graphs, and it can be done with a linear number of calls to an ODD EVEN DELTA oracle.