Christmas Ornaments

Given a collection of Christmas ornaments in the shape of arbitrary
polyhedra (such as, but not limited to cubes, tetrahedra, icosahedra,
etc), suppose each face of each polyhedron is colored depending on
the number of edges of the face.  For example, every four-sided face
(such as a face of a cube) has color number 4, and every triangular
face has color number 3, and in general every n-sided face has color
number n.  Can there be a Christmas Ornament with all sides painted 
a different color?

If we assume that two faces share no more than one common edge, and
that there are a finite number of faces, then the answer is easily
seen to be no.  Simply list, in order, the numbers of neighbors for 
the n faces, so we have a list of n strictly increasing positive 
integers (because no two faces have the same number of neighbors).
Thus at least one of the n faces must border on at least n other 
faces, which is impossible because there are only n-1 other faces.

On the other hand, if we remove the restriction to finite-faced
polyhedra, the answer is yes, because we can define a fractal 
structure that has no two surfaces with the same number of "sides".
To illustrate this, consider a regular tetrahedron, each of whose 
four triangular faces has 3 sides.  Now draw a triangle on one face, 
a square on another, a pentagon on another, and a 9-sided polygon 
on the remaining face.  If we exclude these polygonal regions from 
their respective faces, then the original faces of the tetrahedron 
have 6, 7, 8, and 12 edges, and the excluded regions have 3, 4, 5, 
and 9 edges.  

Needless to say, these "excluded regions" aren't really distinct
faces, because they reside entirely within the planes of the original
faces.  However, we can fix this by building little pyramids on each
of those drawn polygons.  This creates a large number of new
triangular faces, each of which obviously has three sides.  Now we 
can repeat the trick, drawing a 10-sided polygon on one of those
little triangular faces, an 11-sided polygon on another, a 15-sided
polygon on another, and so on.  Then we build little pyramids on 
these polygonal bases and repeat the process.

Thus, defining a solid as the limit of this construction process
carried on indefinitely, we have a fractal ornament with infinitely
many faces, no two of which has the same number of edges.  Notice 
that, even though each face shares only one edge with each of its
neighbors, this construction evades the earlier proof simply because
it's not a finite construction, i.e., there is no finite integer n
equal to the number of faces.

So, in order for the answer to be no, we need to restrict our
polyhedra to those with a finite number of faces.  The question is
whether there exists a finite polyhedron such that no two faces 
have the same number of edges - where "edge" is defined as a maximal
*contiguuous* line segment contained in two specific faces.  Thus, 
two faces can share more than one edge.  (Note that a contiguous 
line segment counts as more than one edge for a given face if it
intersects more than one other face.)  I'll also assume the surface
has genus 2 for the moment.

Let's say a face is "normal" if it shares exactly one edge with 
each of its neighboring faces.  We've seen that if all the faces 
of a solid are normal, it's impossible for all of them to have a
different number of edges.  Now let's consider a solid with one or
more non-normal face(s), (as suggested by David Einstein) such as

                 two edges adjoining 
                 the same face of neighbor
                   ___    ____
                   \  \  /   /
                    \  \/   /
                     \_____/

This implies the existence of two faces X and Y that are adjacent 
over (at least) two separate segments of their common line, as 
illustrated below:

                     Face X

                   e_________f
              c ___/         \
               /   d          \
     A_______B/                \C__________D
              \_______      j__/
              l      g\     /  k
                       \___/
                       h   i

                    Face Y

Faces X and Y share the common edges AB and CD, but they do not 
connect to each other on the segment BC.  Instead, within the region
bounded by the cycle of vertices BcdefCkjihglB we have a set of 
other surfaces.  Let's call a region like this an "anomaly" (borrowed
from crystalography).

Suppose all the surfaces enclosed by X and Y in this anomaly are
normal.  We can then apply our original argument (strengthened by the
fact that no face can have fewer than 3 edges) to show that at least
one of the n faces in this anomaly must have at least n+2 neighbors, 
which is impossible because even counting X and Y there are only n+1 
available neighbors.

Therefore, we conclude that not all the faces in this anomaly can be 
normal, i.e., there must be two faces that share more than one common
edge.  In other words, there must be a (strictly smaller) anomaly 
within the anomaly.  We can now repeat the above argument to prove 
that THIS smaller anomaly must also contain an anomaly, and so on 
ad infinitum.  

This shows again that if we allow the polyhedron to have infinitely
many faces the proof doesn't work - fortunately - because the 
theorem is false in that case.  On the other hand, if we consider
only polyhedra with a FINITE number of faces, then we must at some
stage reach an anomaly that is filled with only normal faces, and 
so those faces cannot all have a different number of edges.

What about the restriction to surfaces of genus 2?  I imposed that
because of the possibility that for a surface of higher genus an
anomaly might "enclose itself", and thereby allow a finite solution,
if the anomaly contains a "wormhole".  There may be some way to close
this loophole (literally!) for surfaces of higher genus, but I don't
see it at the moment.
                                 "God hath given you one face,
                                  and you make yourself another."