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. I was going to suggest you post it as new question, but I see you already did.2010-11-30