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.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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?

share|improve this answer
    
I don't know much about topology; is it possible to provide some outline of the proof? –  Graviton Nov 30 '10 at 11:42
    
en.wikipedia.org/wiki/Mac_Lane%27s_planarity_criterion I don't think there is a rigorous easy proof. –  Max Nov 30 '10 at 11:57
    
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? –  Graviton Nov 30 '10 at 12:16
    
I don't know. I was going to suggest you post it as new question, but I see you already did. –  Max Nov 30 '10 at 15:04

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.