Ages ago, some one asked on this list (I think) for a description of all possible planar graphs with all vertices degree 3, and all faces having 5 or 6 sides (so you can start with a dodecahedron).
Did anyone get round to finding the solution yet? I was just wondering about this again recently; there are about 4 pairs (n,a,b) such that there are infinitely many graphs with n the degree of each vertex, and a, b the possible numbers of sides of a face. for each possible set (n,a,b), I can find loads of infinite families, but I've no idea how to get everything.
Here's a nice little thing: if you have degree 4 vertices, and faces are either squares or triangles, show that you have to have an even number of vertices.
I'd like to know - is this a topological property, or something else? (Cos I didn't prove with with Euler, but it would be nice to know if there was a 'topological' way to prove it, and if it has generalizations, etc)