1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

The answer to your second question is also no: if the graph is a tree, we can't cover any edges by cycles, because there are no cycles. More generally, if we take this graph

enter image description here

or any other graph with a cut edge, the cut edge isn't part of any cycle, so we can't cover all the edges by cycles.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Tanatofobico Apr 27 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.