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
    Do you want to ask about something that you didn't understand in the MathsOverflow answer?2010-08-01
  • 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.

  • 1
    Asked by the same asker!2010-08-01
  • 0
    @Doug, I dont' quite understand the solution there. And I think that they actually understood my question.2010-08-02
  • 0
    @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.2010-08-05
  • 0
    @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 first step you don't understand in the above argument.2010-08-05
  • 0
    @doug, For starters, what is `K3,3` and `K5`? Sorry if I sound dumb, but I am unfamiliar with all the graph theory terminologies.2010-08-05
  • 0
    @Ngu Soon Hui: To get a picture of $K_{3,3}$, put three dots on the left side of your paper and three dots on the right side, then draw an edge to connect every dot on the left to every dot on the right. If the left vertices are 1,2,3 and the right vertices are A,B, and C, then the edges are 1A, 1B, 1C, 2A, 2B, 2C, 3A, 3B, and 3C. You can see several pictures of $K_{3,3}$ here: http://mathworld.wolfram.com/UtilityGraph.html. To get $K_5$, put five dots on a new sheet of paper and draw every possible edge. A picture of $K_{5}$ is here: http://mathworld.wolfram.com/CompleteGraph.html2010-08-05
  • 0
    Well, I'll say some more about the proof next week. For now, I must get back to conferencing.2010-08-05
  • 0
    A few questions before I continue: 1. How well do you understand the cycle basis description that your question links to? (http://www.mathreference.com/gph,basis.html) 2. What motivated you to consider the problem you have asked about?2010-08-08
  • 0
    @doug, actually I don't understand much about the cycle basis description. 2. Basically it is a circuit theory problem , [Kirchoff voltage law](http://www.allaboutcircuits.com/vol_1/chpt_6/2.html)), in computing the voltage and current, I would have to make sure that in a circuit, the cycle basis I form ( for the KVL purpose) must not have any of the edge having more than 2 cycles connected to it, or else my numerical scheme will run into problem. This is what motivated me in asking this question.2010-08-11
  • 0
    Well, let's look at $K_{3,3}$ Call the vertices on the left A, B, and C and the ones on the right D, E, and F. To form a cycle basis, first choose a spanning tree. I'll choose the tree with edges AD, AE, AF, BD, and CD. Each edge of $K_{3,3}$ not in that tree completes a cycle. Edge BE completes the cycle BE-AE-AD-BD, which I'll call $C_{1}$. Edge BF completes the cycle $C_{2}$, which is BF-AF-AD-BD. Edge CE completes cycle $C_{3}$, which is CE-AE-AD-CD. Edge CF completes $C_{4}$, which is CF-AF-AD-CD. These cycles form a cycle basis. Note that AD is in all of these cycles. (cont.)2010-08-11
  • 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