Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

The degree of a vertex is defined as the number of edges touching it. Let’s define 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).

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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.

Your graph has this property.

This is probably not the best way to solve this problem. but it uses a nice definition of face. I also didn't work through 4 and 5. because I couldn't think of a way to do them nicely, and I figured you only wanted help coming up with a proper strategy.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.