3
$\begingroup$

This is a slightly different question than the one asked here.

I understand that for non-planar graph there are edges in the graph which has more than 2 cycles sharing on it. But for planar graph, can we prove that it is always possible to find a complete set of cycle basis that each edge is shared by at most 2 cycles?

1 Answers 1

3

This is of course true, with the basis cycles being boundaries of the bounded faces (after killing off all pairs {edge e, reverse of edge e}).

Are you looking for a rigorous proof? It should follow from the argument establishing the fact that there are such things as faces etc (see for example chapter 4 here). How much of relevant topology are you willing to assume?

  • 0
    I don't know much about topology; is it possible to provide some outline of the proof?2010-11-30
  • 0
    http://en.wikipedia.org/wiki/Mac_Lane%27s_planarity_criterion I don't think there is a rigorous easy proof.2010-11-30
  • 0
    if the answer is yes to the question above, is there any method that can construct such a set of cycles for any planar graph?2010-11-30
  • 0
    I don't know. I was going to suggest you post it as new question, but I see you already did.2010-11-30