Problem:
A cactus is a finite simple connected graph where no two cycles share an edge. Show that in a nonempty cactus, there must exist a vertex which is part of at most one cycle.
Solution
Solution:
Let be the original cactus. For every cycle in , arbitrarily remove one of its edges, yielding a new graph . Observe that since the cycles are edge-disjoint, we removed exactly one edge from every cycle, meaning the graph stays connected. However, there are no longer any cycles, so is a tree.
Now consider any leaf of (note that any nonempty tree must have a leaf). If is the only vertex in the graph we're trivially done, since then was the only vertex in . Otherwise has degree . If was originally a leaf of , we're done. If not, observe that in the process of turning into , a vertex's degree cannot decrease by more than half, because for every cycle that a vertex is part of in , it gains a degree of , but can only lose degree from an edge of that cycle being removed. Therefore, the original degree of in was at most , meaning it could have been part of at most cycle, as desired.