Why does induction procedure of Euler characteristic fail for non-convex polyhedra? What am I missing? Euler characteristic of convex polyhedra is always $V-E+F=2$. 
Induction procedure reduces edges and vertices until we are down to one vertex whose $V-E+F=2$ and hence you are done.
The same induction procedure should also work for non-convex polyhedra and reduce to one vertex. So why does the induction procedure not work for non-convex polyhedra(giving $\neq 2$ values sometimes)? 
Please use elementary language in your description (for example, a talk to freshmen).

The proof I know that $V-E+F=1$ for convex polyhedra starts by removing a face, then stereographically projecting the complement into the plane, to get a convex polygon in the plane subdivided into smaller polygons. Then one removes pairs of edges and vertices or edges and faces until you get down to a point. 
The thing that fails in the nonconvex case is that after you remove a face, you can't necessarily project the rest into the plane. For example, if your polyhedron is shaped like a torus (so it has a hole in it), once you remove a face, the rest of the polyhedron can not be embedded in the plane. 
