# Graph Theory Question Confused

Im confused to this question. Can someone lead me in the proper way?

The degree of a vertex is deﬁned as the number of edges touching it. Let’s deﬁne in an analogous way the degree of a face to be the number of edges encountered when we complete a walk around its boundary. What happens if we add up the degrees of all faces (note: this includes the outer face too).

-

There are some obvious situations where this doesn't make much sense, like a graph that is not embedded in the plane. But, assuming you have such a thing, as you trace around each face, each edge in the face is counted once. And, as you trace around all faces, each edge is counted once each in two different faces. So, clearly, the total will be 2 times the number of edges, which is equal to the sum of the degrees of vertices by the handshaking lemma.

-

I disagree with the notion that the graph has to be imbedded in the plane for this problem to make sense. It merely needs to be imbedded in a compact surface, and since all finite graphs have the property that they can be imbedded in a surface, then the result should hold for all finite graphs (since it is indeed $2E$). it is also clear that each edge will not generally be counted once per face. An acyclic graph for instance only has one face. and a traversal of the boundary requires you to walk each edge twice.

1 Every surface has a triangulation. This is hard to prove, but it comes from a topological result on the classification of surfaces.

2 Your graph is homomorphic to a subgraph of some triangulation. I do not remember what this theorem is called.

3 a triangulation quite easily has this property. It falls right out of the definition, in that every edge shares precisely two faces.

4 removing an edge common to two faces causes all other edges common to them to be double counted in the traversal of the boundary.

5 subdividing/unsubdividing an edge does not change.