RO-TST 2005 Problem 17

We consider a polyhedra which has exactly two vertices adjacent with an odd number of edges, and these two vertices are lying on the same edge.

Prove that for all integers $n\geq 3$ there exists a face of the polyhedra with a number of sides not divisible by $n$ .