A random Eulerian triangulation is a random triangulation where an even number of triangles meet at any given vertex. We argue that the central charge increases by one if the fully packed O(n) model is defined on a random Eulerian triangulation instead of an ordinary random triangulation. Considering the case n -> 0, this implies that the system of random Eulerian triangulations equipped with Hamiltonian cycles describes a c=-1 matter field coupled to 2D quantum gravity as opposed to the system of usual random triangulations equipped with Hamiltonian cycles which has c=-2. Hence, in this case one should see a change in the entropy exponent from the value gamma=-1 to the irrational value gamma=(-1-\sqrt{13})/6=-0.76759... when going from a usual random triangulation to an Eulerian one. A direct enumeration of configurations confirms this change in gamma.