# Problem with set of cycles covering a graph

My question is the following: is there always, for any non-directed graph $$G$$, a choice of generators of the fundamental group or, more in general, a set of cycles, covering the graph and with the property that no edge is shared by more than two cycles?

In case it isn't always possible to find such a set, can you provide a counter-example?

The answer to your first question is no: for the complete graph $$K_n$$, the fundamental group needs $$\binom n2 - (n-1) = \binom{n-1}2$$ generators. Each one uses at least $$3$$ edges, for at least $$3\binom{n-1}{2}$$ edges total. But $$3\binom{n-1}{2} > 2\binom n2$$ for $$n>6$$, which means that at least one of the $$\binom n2$$ edges is used more than twice.
• Thank you for your answer! I forgot to specify $G$ is a bridgeless graph. What about a 3-regular graph? would it be possible then to always find such a set of cycles? – Tanatofobico Apr 27 at 11:50