Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a graph with a list of edges, is it possible to always construct a set of cycle bases for those edges, such that each and every edge is shared by at most 2 cycle bases?

The above question assumes that each and every edge must somehow belong to at least one cycle. IN other words, there is no vertex that is connected to one and only one edge.

share|improve this question
2  
Here's an extensive survey article on cycle bases: math.uga.edu/~caner/09vigre/SurveyCyclebases.pdf –  Doug Chatham Jul 6 '10 at 13:54
4  
And it cites a theorem of MacLane (1937) to the effect that a graph has such a cycle basis if and only if it is planar. –  BS. Jul 6 '10 at 14:41
    
@BS, do you have a refernece on that? –  Graviton Jul 7 '10 at 7:01
    
en.wikipedia.org/wiki/Mac_Lane%27s_planarity_criterion says: S. Mac Lane, A combinatorial condition for planar graphs, Fund. Math. 28 (1937), 22–32. –  Thorny Jul 7 '10 at 9:46
    
Additional reference. Available online and shorter than the Mac Lane paper: ams.org/journals/proc/1973-037-02/S0002-9939-1973-0313098-X/… –  Doug Chatham Aug 2 '10 at 15:07

1 Answer 1

up vote 5 down vote accepted

Consider the complete graph on 7 vertices. It has 21 edges, so any set of cycles that utilizes each edge at most twice has size at most 42/3=14. But the cycle space of the graph has dimension 21-7+1=15, so you cannot have a basis with the requested property.

share|improve this answer
    
I don't follow your logic, is there any nonintuitive properties of graphs and edges that you make use of when you make this deduction? –  Graviton Jul 7 '10 at 7:01
    
I implicitly use that all cycles contain at least 3 edges, and that the dimension of the cycle space is the number of edges exceeding that of a tree with the same vertices. Both facts are straightforward, could you please elaborate on where exactly you have problems? –  Thorny Jul 7 '10 at 9:44
    
Thorny, first are you saying that you assume a graph with 7 vertices and 21 edges? If yes, then your reasoning at most hold for that case, what about other case? Second, how do you actually define dimension of the cycle base? –  Graviton Jul 7 '10 at 12:49
1  
I answer the question "In a graph, is it always possible to construct a set of cycle bases, with each and every edge Is shared by at most 2 cycle bases?" in the negative, so one counterexample is all it takes. If you wanted to ask a more precise question, then BS's lead is what you should read. As for your other question, please consult en.wikipedia.org/wiki/Cycle_space . –  Thorny Jul 8 '10 at 7:21
    
@Thorny, I still don't quite follow your logic. If you may, you might want to construct a diagram that answers my question negatively in graphical terms, that would be tremendously helpful. Sorry and thanks a lot! –  Graviton Jul 13 '10 at 14:37

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.