The formula $VE+F=2$ is so simple that I can't believe that it was really Euler (or perhaps Descartes) who first observed it (I mean the formula itself in some generality, not necessarily a valid proof). To have a concrete question: Is there any reference to this formula in ancient mathematics?

there is no doubt the answer to your question is "no"; for a wonderful and scholarly recent book on the whole story, see Euler's Gem: The Polyhedron Formula and the Birth of Topology by David Richeson.
Centuries later, we remain astonished. 


Today almost nobody shares anymore old Leibnitz' optimistic idea There is no ignorabimus in mathematics (in Hilbert's words). We know that there are true facts in mathematics that will never be proved, either because our maths society (if not the whole mankind) will extinguish before, or because the shortest proof has by far more symbols than there are atoms in the universe, or just because there is no proof at all. Yet, it seems we still reject the analogous ignorabimus about questions in the history of mathematics. We tend to think our knowledge of what the ancients knew is quite detailed: If some piece of maths is missing from the ancient sources, the reason has to be, just because it was not known, otherwise, it would certainly had arrived to us in some way. This optimistic point of view is unreasonable too, as it has been proved, among others, by the work of Lucio Russo. It's a fact that a relevant part of what we know about ancient scientific knowledge came to us in the most erratic and totally unpredictable way through fires, floods, and wars. Fundamental Archimedes's Method survived many centuries in a monastry only because its parchment happened to be useful to write a religious text, but in the meanwhile it happened not to be completely erased. It was discovered by chance in 1840 and attributed to Archimedes only in 1906, and lost again till 1998. A popular striking example is the story of the Schroeder numbers. See this beautiful article by Richard Stanley . Before the year 1990 no or few examples of Hellenistic combinatorics were known. Then the numbers 103,049 and 310,952 were noticed in a passage of Plutarch, proving, as irrefutably as fingerprints, Hellenistic combinatorics was by far more advanced than ever thought before. Had Plutarch omitted that mathematical aside note, today conjecturing the knowledge of the Schroeder numbers in the Greek mathematics should be considered at least uncalled for, exactly as it is conjecturing the knowledge of the Euler formula. Of course, the former fact does not make the latter conjecture more likely to be true. We can only compare the two and say that Euler formula is elementary and simple enough that it could be wellknown and proved. I think a more reasonable question is: whether Euler formula was missed or not by the advanced Hellenistic mathematics, how was that it was not discovered/rediscovered/remembered till Euler? Possibly, the reason is, till that moment that formula had not such a relevant role as it had later. On the contrary, say, the properties of the parabola have always been something of interest, so that it was never forgotten despite centuries of wars (and maybe even thanks to wars: to throw projectiles). In conclusion I somehow differ from Carlo Benakker's opinion, and think that a more cautious, though less satisfying answer to this question would be: no, as far as we know; and if the true answer is no, we will probably never know. If the true answer is yes, we may hope in a new achievement of historiography that gives us a proof, like in the case of Schroeder numbers. 


Once I was lecturing to high school students about this theorem. My proof began with the words: "suppose that the net is drawn on a surface of a rubber ball...". One student asked: "Did rubber exist at the time of Euler?" I think the moral of this story is that the very statement of the question was foreign to ancient Greek mathematics. Did they have a definition of ARBITRARY polytope? Or even an arbitrary convex polytope? I doubt it. Descartes proof was earlier than that of Euler, and his statement was in terms of solid and plane angles (which is equivalent to the GaussBonnet theorem, but stated in terms of elementary geometry). I think it was Euler who recognized for the first time that we have a topological fact here. And this was a great insight. Like the problem of the same Euler about the Konigsberg bridges. It is not difficult, but before Euler these things apparently were not considered part of mathematics. That's why these questions were not raised in antiquity. EDIT. Many things were not discovered for the simple reason that no one was looking for these things. Let me give a more recent example. Could Fermat, Descartes, Huygens, Euler, etc. discover linear programming and simplex method? There is no doubt they could. After all, this is elementary mathematics which can be easily taught in high school. But look what had really happen. Fourier had a paper on systems of linear inequalities (where he invented what is called FourierMotzkin elimination nowadays). And in the end of XIX century (!) the editor of Complete works of Fourier had to APOLOGIZE for including this paper: he wrote that "every work of such a grand master has to be included", where "every" evidently means "even such trivial nonsense":) And linear programming became a part of mainstream mathematics only during WWII, when it was really needed. 

