Why doesn't the Euler's polyhedral formula work? So apparently, the infamous $V+F-E=2$ doesn't work for some, but not all non-convex polyhedra, e.g. the great dodecahedron.
Is there some sort of rule describing which non-convex polyhedra Euler's formula holds true for and which it doesn't? I'd guess this has to do with the intersecting nature of these shapes, is this correct? If so, how does this criteria come in to play in proofs of the theorem?
 A: The best answers to your question require some knowledge of first year algebraic topology, and are stated in the language of homotopy equivalence and homeomorphism. I'll give a few answers in that vein.
Just to be clear, I'll be talking about polyhedra which are 2-dimensional, so they are composed of vertices, faces, and edges alone. There do exist higher dimensional generalizations of polyhedra, and higher dimensional generalizations of some of the theorems I discuss, and what I am doing is to specialize those general theorems to the case of 2 dimensions.
The first theorem says that the value of $V+F-E$ depends only on the homotopy type of the polyhedron: 


*

*If $P_1$, $P_2$ are two polyhedra that are homotopy equivalent to each other, then 
$$V_1 + F_1 - E_1 = V_2 + F_2 = E_2
$$


The next theorem is a more informative version of the previous one, and it says that the value of $V+F-E$ may be calculated using the ranks of the homology groups of the polyhedra:


*

*$V+F-E = \text{rank}(H_0(P)) - \text{rank}(H_1(P)) + \text{rank}(H_2(P))$


The previous theorem, augmented by some hard topological work, gives a complete answer to your question in the case of a polyhedron which is connected and is a 2-dimensional manifold, meaning that it is locally homeomorphic to the Euclidean plane. The answer is stated in the language of topological classification, where the goal is to decide when two topological spaces are homeomorphic to each other. This theorem also requires what is implicit in your question, namely that $P$ is a polyhedron sitting inside 3-dimensional Euclidean space:


*

*If the polyhedron $P \subset \mathbb{R}^3$ is a connected 2-dimensional manifold then $V+E-F$ is an even integer $\le 2$, and furthermore:


*

*$V+E-F=2$ if and only if $P$ is homeomorphic to the sphere.

*$V+E-F=0$ if and only if $P$ is homeomorphic to the torus.

*$V+E-F=-2$ if and only if $P$ is homeomorphic to the double torus.

*In general, the integer $g \ge 0$ which satisfies the equation $V+F-E=2-2g$ is called the genus of $P$, and any two $P$'s having the same genus are homeomorphic to each other. 
As one might guess from all of this, the quantity $V+F-E$ is very important to topologists, so important that it has its own name --- the Euler characteristic --- and its own notation $\chi$.
A: Euler's formula also holds for several classes of non-convex polyhedra, like star-convex polyhedra, for example. "Convexity" as an assumption is to a certain extend accidental, as is explained here. On the other hand, Euler's formula certainly does not hold for all polyhedra. Consider polyhedra with holes to see this.
