In a chart, is it constantly feasible to construct a set of cycle basis, with every side Is shared by at the majority of 2 cycle bases?

Allow's claim we have a chart, with a checklist of sides and also vertexes $(E,V)$, all the vertexes are attached to at the very least one side at one end There are several means a full set of cycle basis can be figured out from it.

Currently the concern is, is it constantly feasible to locate a full set of cycle basis that each side is shared by at the majority of $2$ cycles?

Modify: There is a mathematical argument confirming why it is not feasible. Yet unquestionably such a very abstract thinking is a little bit tough for me to realize. I would certainly value if a person can give a visual instance of such a chart.

0
2019-05-04 16:26:45
Source Share
Answers: 1

The inquiry was addressed in the adverse 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 kind of non-planar chart where every side becomes part of at the very least one cycle. Below's a reference : P. V. O'Neil, Proc. AMS, 37 (2), Feb. 1973, 617-8

I'll duplicate the argument below. Take a nonplanar chart with every side in at the very least one cycle. If that had a cycle basis like the one you desire, after that we can create one for $K_{3,3}$ or $K_{5}$. Intend we had a basis for $K_{3,3}$. There are 4 cycles because basis. (A cycle basis has m-n +1 components, where m is the variety of vertices and also n is the variety of sides. ) Additionally, take the binary amount of the 4 cycles. The 5 cycles include every side specifically two times, so there are a total amount of 2 $\cdot$ (variety of sides ) = 18 sides in those 5 cycles. Yet each cycle contends the very least 4 sides, so the 5 cycles have to contend the very least 20 sides. Opposition.

Currently allow's consider $K_{5}$. A cycle basis has 6 cycles. Additionally take the binary amount. The 7 cycles include each side specifically two times, so there are 2 $\cdot$ (variety of sides ) = 20 sides in the collection. Yet each cycle contends the very least 3 sides, so the 7 cycles contend the very least 7 * 3= 21 sides. Once more, an opposition.

0
2019-05-07 23:53:24
Source