Zero Obstructed vertex induced subgraphs Let $G=(V,E)$ be a $3$-regular graph. Let a vertex induced subgraph of $G$ be $i$ extendible if and only if it has both the following properties:  


It has no isolated vertices.  
It is possible to add $i$ vertices to it without implying (by the very definition of vertex induced subgraph) the introduction of any new edge (in other words, it is possible to add $i$ isolated vertices).  


Clearly, if a vertex induced subgraph is $i$ extendible it is also $j$ extendible for any $j &lt; i$. 

Now, let a vertex induced subgraph of $G$ be $i$ obstructed if and only if it is $i$ extendible but not $i+1$ extendible.

I'm interested in $0$ obstructed vertex induced subgraphs.


  Questions  
  
  
  Let $N$ be the number of $0$ obstructed vertex induced subgraphs of $G$. Is $N$ polynomially bounded in the size of $G$? I believe yes (and I've made some empirical tests that seem to suggest so), but so far I was unable to prove it.
  If the answer to question 1. is no, is it nevertheless possible to compute $N$ in polynomial time?  
  If the answer to question 2. is no, is it nevertheless possible to compute $N\ mod\ 2$ in polynomial time?
  


I'm curious to know if anyone already dealt with $0$ obstructed vertex induced subgraphs previously, how he encountered them in the first place, and what is known about them.  

Another way to express question 1. is the following: which is the maximum number $\alpha$ of vertices that can be removed from $G$ without making it $1$ extendible? My sensation is that $\alpha \in O( log\ |V| )$, as I'm inclined to believe that $\alpha$ is strongly related to the diameter of $G$.
Sorry this is too long for a comment :)

Maybe the complete graph is a trivial graph but it illustrates that e.g. graphs $G = (V,E)$ with large cliques of size $\Omega(\vert V \vert)$ also have exponentially many $0$ obstructed induced subgraphs. And I don't think that $N$ can be easily computed in such graphs. 

I also think that 3-regularity doesnt help: Let $A$, $B$ be a partition of $V$ each of size $\vert V \vert /2$. The induced subgraph consisting of nodes from either $A$ or $B$ is a cycle and the edges between $A$ and $B$ form a perfect matching. This graph is $3$-regular and every induced subgraph consisting of at least all nodes in $A$ or all nodes in $B$ is $0$ obstructed.