2
$\begingroup$

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.

  • 0
    @Casebash. Yup. I dont' quite understand the solution there. And I think that they actually understood my question.2010-08-02

1 Answers 1

3

The question was answered in the negative on Math Overflow. See https://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.

  • 0
    Other cycle bases are formed from other spanning trees, and they all will have at least one edge in three or more of the basis cycles. Now, when the proof above refers to "binary sum", it means to take those edges that appear in an odd number of the cycles of the basis. For the example cycle basis that would be $C_{5}$, the cycle formed by edges BE,BF,CE, and CF. We should probably continue this discussion in email. Email me at d.chatham@moreheadstate.edu2010-08-11