Coding Sequences and Euler's Formula for Graphs on Surfaces

摘要

Coding sequences are generalization of Eulerian tours of graphs, originally designed for communication of examples by students working on conjectures of the first classroom version of Graffiti. For Eulerian graphs, coding sequences are simply sequences of vertices in the order in which they are encountered in the Eulerian tours of edges of these graphs. One of the first findings of this version of Graffiti was a formula suggesting a new, yet simple and intuitive proof of Euler characteristic formula for planar Eulerian graphs. We shall discuss here an extension of this idea to arbitrary planar graphs and to 2-cell embedding of graphs into compact surfaces without boundaries.