I have not a complete proof yet Anyway, we can easily prove that there is a triangular face (here we use that there are two odd vertices, but don't use that they are connected), so we are only to prove that it is impossible that each face has a number of sides, which is divisible by 3.

how does that finish the problem? the problem says "for all $ n \geq 3 $... "

If we have a triangular face it means that number of its sides is not divisible by any $n\geq 4$ !

I realized that even don't need what I wrote above. Draw this planar graph on the plane. Suppose all faces are divisible by $n$. Take an arbitrary face and remove all its edges! We will obtain a new planar graph and all its faces will be divisible by $n$ again (note that we need properly count number of sides in each face; see remark 2). We also see that new graph contains only two odd vertices. Perform it step by step. Finaly we will obtain a planar graph consisting the only edge, which connects two odd vertices, but in this case we have the only face with two sides. Remark 1. We need that two odd vertices are connected for the last step. Otherwise we will obtain a chain, so number of sides of the only face could be divisible by some number $n\geq 3$. Remark 2. The number of sides on the yellow face in the planar graph below is 9. I hope it is correct.

Attachments:

I think I can proe that thing about divisibility with $3$, Myth: First of all, it suffices to assume that all our faces are triangular (I'll say why at the end). Assume we have managed to orient the edges so that all the triangles, except, maybe, for one of them, is oriented, either in a clockwise or an anticlockwise direction. Then the last one must also be oriented, because we can write the clockwise cycle on the dges of that triangle as a sum of cycles of the other triangles, and those are all $0$ (by a cycle I mean the value we get when we go around the triangle in the mentioned direction and we put a $1$ for edges we traverse directly, and a $-1$ for edges we traverse inversely). Now, let's look at the polyhedron obtained from our polyhedron by deleting the common side of the two odd vertices. We have a polyhedron with even vertices only. We can color it chessboard-style (this need further justification, but I think that's not hard to give), and then orient each black face in a clockwise direction. The white faces will automatically be oriented in a counterclockwise direction. We go back to our original polyhedron, and orient the "bad" edge however we want. We have a polyhedron in which exactly one trianlge is not oriented, and that's a contradiction. Now, to see why we can restrict our attention to triangles, given a convex polygon with $3k$ vertices, it's easy to triangulate it so that each vertex lies on an even number of edges in the triangulation, so we do this with each face of our polyhedron. Edit: oops.. I didn't see your last post.

oh, i see what you mean now.

Another solution: Take the planar graph, remove the troubling edge, and colour this in red and blue, with no 2 neighboring faces coloured the same. Only one face won't have the no. of edges divisible by $n$, i.e. the one obtained by joining the 2 faces that had a common edge the one removed. Now let's say this face is colured blue. Count the edges after all red faces. We will have all the edges counted once this way, so $m-1$ is divisible by $n$. On the other hand counting these on the polyhedra we obtain $2m=M_n$, imposible.