If an edge is part of a cycle, is there always some spanning tree where the cycle is a fundamental cycle and the edge is a chord

graph theorytrees

I understand that there is a fundamental cycle for each edge missing in the spanning tree (the chords). It seems by observation, that given some edge one can find every cycle that the edge belongs to, and then each of those cycles will be a fundamental cycle in at least one spanning tree in which that edge is missing. This can be seen in pic related for example.

enter image description here

Any guidance or hint on how to prove or disprove this would be greatly appreciated.

Best Answer

This amounts to finding a spanning tree containing every edge in $C-e$, where $C$ is your chosen cycle and $e$ is your chosen edge. Can you see how to find one?

Starting from $C-e$, you can just greedily choose edges in such a way that the new edge does not create a cycle with the previously chosen ones. If you keep repeating this, you will end up with a spanning tree (or a spanning forest if the graph is not connected).

If you are (or will ever be) familiar with matroids, then you should note that the exact same reasoning works for any matroid.

Related Question