# In a graph, is it always possible to construct a set of cycle basis, with each and every edge Is shared by at most 2 cycle bases?

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.

-
@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

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.

-
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