550.100 Homework from October 30, 2012 Problem 1: Suppose that S R3 is a surface, and that a graph G is 2-cell-embedded in S. Additionally suppose that each of the vertices of G is an endpoint for exactly 4 edges of G, and that each of the faces of the embedded graph G in S has a boundary consisting of exactly 4 edges. (For example, see the attached gure for a 2-cell embedding of one particular graph in a particular surfacea toruswith these additional conditions on the vertices and faces.) Prove that, in fact, the surface S must be topologically equivalent to a torus. (Hint: Use Euler-Poincare Theorem) 1 Background is determined up to homeomorphism by its genus g (the number of \"handles\" that are \"added\" to a sphere) g=0 g=0 (human cerebral cortex) g=1 g=1 g=2 g=2 1 Background A 2-cell embedding of a graph G on surface S is an embedding where no edges cross, and each face may be \"contracted\" to a point. n = 32, e = 60 f = 30, g = 0 Theorem: (Euler-Poincare) For 2-cell embedding of graph G on surface S of genus g, having n vertices, e edges, and f faces n - e + f = 2 - 2 g. , the \"Euler characteristic\" of surface S 2