The following is an exercise from an introductory course on combinatorics.
Let $G$ be a finite simple graph, and color its edges such that every color appears exactly twice. Assume that from every vertex there are at least $4$ different colors. Prove that it is possible to remove some edges such that there will not be any duplicate colors remaining, and yet every vertex will still have at least one neighbor.
In other words, we are looking for a spanning subgraph without isolated vertices and with distinct colors.
I tried to remove edges in an explicit algorithm and avoiding the removal of edges that will make the process stuck, but the order of removal seems to be too dependent on the topology of the specific graph at hand. I also tried to remove edges independently with some probability $p$, but there seem not to be any $p$ that works for both conditions. As a sidenote, I believe that the course from which this exercise is taken does not assume knowledge of the probabilistic method.