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.

Let's say we have a graph, with a list of edges and vertexes (E,V), all the vertexes are connected to at least one edge at one end. There are many ways a complete set of cycle basis can be found out from it.

Now the issue is, is it always possible to find a complete set of cycle basis that each edge is shared by at most 2 cycles?

Edit: There is a mathematical argument proving why it is not possible. But admittedly such a highly abstract reasoning is a bit hard for me to grasp. I would appreciate if someone can provide a graphical example of such a graph.

share|improve this question
    
@Casebash, question updated. –  Graviton Aug 1 '10 at 13:09
    
Do you want to ask about something that you didn't understand in the MathsOverflow answer? –  Casebash Aug 1 '10 at 21:03
    
@Casebash. Yup. I dont' quite understand the solution there. And I think that they actually understood my question. –  Graviton Aug 2 '10 at 6:54

1 Answer 1

up vote 3 down vote accepted

The question was answered in the negative on Math Overflow. See http://mathoverflow.net/questions/30759/in-a-graph-is-it-always-possible-to-construct-a-set-of-cycle-bases-with-each-an


Edit:

We get a counterexample from any non-planar graph where every edge is part of at least one cycle. Here's a reference: P. V. O'Neil, Proc. AMS, 37 (2), Feb. 1973, 617-8

I'll repeat the argument here. Take a nonplanar graph with every edge in at least one cycle. If that had a cycle basis like the one you want, then we could generate one for $K_{3,3}$ or $K_{5}$. Suppose we had a basis for $K_{3,3}$. There are 4 cycles in that basis. (A cycle basis has m-n+1 elements, where m is the number of vertices and n is the number of edges.) Also, take the binary sum of the four cycles. The five cycles include every edge exactly twice, so there are a total of 2 $\cdot$ (number of edges) = 18 edges in those five cycles. But each cycle has at least 4 edges, so the five cycles must have at least 20 edges. Contradiction.

Now let's look at $K_{5}$. A cycle basis has 6 cycles. Also take the binary sum. The 7 cycles include each edge exactly twice, so there are 2 $\cdot$ (number of edges) = 20 edges in the collection. But each cycle has at least three edges, so the 7 cycles have at least 7*3=21 edges. Again, a contradiction.

share|improve this answer
1  
Asked by the same asker! –  ShreevatsaR Aug 1 '10 at 14:38
    
@Doug, I dont' quite understand the solution there. And I think that they actually understood my question. –  Graviton Aug 2 '10 at 6:54
    
@Doug, this piece of mathematical argument is quite hard for me, is it possible to construct a graphical counter example for such a graph? I would understand it intuitively after failing to find such a cycle basis for that graph. –  Graviton Aug 5 '10 at 5:46
    
@Ngu Soon Hui: So you want pictures to help you understand a counting argument? Unfortunately, I'm at a conference for the next several days and won't have time to construct such pictures. It might help those trying to help you if you'd identify the <b>first</b> step you don't understand in the above argument. –  Doug Chatham Aug 5 '10 at 9:36
    
@doug, For starters, what is K3,3 and K5? Sorry if I sound dumb, but I am unfamiliar with all the graph theory terminologies. –  Graviton Aug 5 '10 at 13:58

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.