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).
 A: 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. 
A: First, there is not just one induction proof of Euler's theorem. David Eppstein has gathered
20 distinct proofs at this link.

 
 
 
 
 


Second, most of the induction proofs do work for nonconvex polyhedra (but see below).
The one illustrated above (mentioned by @GrumpParsnip; figure from Eppstein's website) does not because it
uses stereographic projection. But if you instead just imagine topologically stretching
out one face boundary to become the outer boundary in the plane (rather than geometrically projecting),
the same proof works.

Third, as @Mariano Suárez-Alvarez hints, there are nonconvex polyhedra for which
the Euler characteristic is not $2$ (and for which some of the 20 proofs mentioned
above do not work). Only those polyhedra homeomorphic (stretchable) to
a sphere have $=2$ as the right-hand-side. If the "polyhedron" has a hole (like a torus)
or a cavity, the right-hand-side is $\neq 2$.
