  We prove that finding a $k$-edge induced subgraph is fixed-parameter
tractable, thereby answering an open problem of Leizhen Cai. Our algorithm is
based on several combinatorial observations, Gauss' famous \emph{Eureka}
theorem [Andrews, 86], and a generalization of the well-known fpt-algorithm for
the model-checking problem for first-order logic on graphs with locally bounded
tree-width due to Frick and Grohe [Frick and Grohe, 01]. On the other hand, we
show that two natural counting versions of the problem are hard. Hence, the
$k$-edge induced subgraph problem is one of the rare known examples in
parameterized complexity that are easy for decision while hard for counting.
