NP complete graph problems about structural properties
I think there are lot of similar problems. Here are two in vertex version and one in edge version:

1) Does a given graph have an independent feedback vertex set? (we don't care about the size of the set). 
This problem is NP-complete; the proof can be derived from the proof of Theorem 2.1 in 
Garey, Johnson &amp; Stockmeyer.

2) Does a given graph have a vertex cover that induces a tree? (we don't care about the size of the set). 
This paper 
gives an NP-completeness proof for this problem (Theorem 2); even for bipartite graphs.

3) Does a given graph have a dominating edge set the edges of which form an induced $1$-regular subgraph? 
(also known as dominating induced matching or efficient edge dominating; the vertex version is given in the 
second answer by Mohammad. 
Again, we don't care about the size of the set). 
This problem is NP-complete (well-known, first proved here), even for planar bipartite graphs. 

The first two problems are particular examples of the problem class called stable-$\pi$: 
Let $\pi$ be a graph property. Does a given graph have a vertex cover satisfying $\pi$? 
More NP-complete cases as well as polynomially solvable cases can be found in 
this 
and in this paper 
(and the refs given there) .