this is perhaps one of the coolest problems in graph theory I met so far. The problem states:

PROBLEM: There is a flu epidemic in elf city. The course of the disease is always the same. An elf is infected one day, he is sick the next, recovered and immune the third, recovered but not immune thereafter. Every day every elf who is not sick visits all his sick friends. If he is not immune he is sure to catch flu if he visits a sick elf. On day 1 no one is immune and one or more elves are infected from some external source. Thereafter there is no further external infection and the epidemic spreads as described above. Show that it is sure to die out (irrespective of the number of elves, the number of friends each has, and the number infected on day 1). Show that if one or more elves is immune on day 1, then it is possible for the epidemic to continue indefinitely. (All Russian Math Olympiad 1980)

As a first hint one shall think, what is really the difference of the following two graphs?

tree (no-cycle)

a cycle exists