The famous statement that
Only five convex regular polyhedra exist.
is usually proven as follows:
Let $P$ be a convex regular polyhedron with
- V vertices,
- E edges and
- F faces.
Moreoever, let
- n be the number of edges of each face and
- c be the number of edges which meet at a vertex.
Then $F=\frac{2E}{n}$ and $V=\frac{2E}{c}$ and $c\geq 3, n\geq 3$.
Substituting this into Euler's polyhedron formula $$ V-E+F=2, $$
and doing some easy calculations, one gets that only
$$ (V,E,F)\in\{(4,6,4),(8,12,6),(20,30,12),(6,12,8),(12,30,20)\} $$ are possible combinations.
So far, so good.
But where do we need that $P$ is convex and regular?
(I think the regularity is at least used for $n\geq 3, c\geq 3$, isn't it?)
As already said in the comments, regularity means being composed of equal faces, thus enabling to connect the numbers $V$, $E$ and $F$ by some algebraic relations. This is the left part of Euler's identity $$V-E+F=2$$ Now, convexivity is, in fact, the right-hand side.
In general, for a surface $S$, the formula reads $$V-E+F=\chi(S)$$ where $\chi$ is the Euler characteristic (defined by the equation above or, alternatively, by the alternating sum of dimensions of homology groups).
If a polyhedron is convex, it can be proven that it's boundary is homeomorphic (topologically equivalent) to a sphere $\mathbb{S}^2$, and $\chi(\mathbb{S}^2)=2$, providing the right part of Euler's equation.
So, convex is just a simplification; the classification really works for all polyhedra homeomorphic to a ball. For some other topology, a different classification may arise.