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

graphs fun

It’s been a long since I posted something. I just started reading the marvellous book about graphs: Graph Theory by Bin Xiong,Zhongyi Zheng. There are some really good problems with solutions too and the basic theory. Graph problems are about stating the problem, fixing vertex connectivity, coloring edges/vertices and pretty much using the imagination to identify the constraints of the given conditions. The book’s chapters are: Definition of Graphs, Degree of vertex, Trees, Turin’s theorem, Euler-Hamilton graphs, Planar graphs and Ramsey applications. A nice problem with coloring:

PROBLEM: Nine mathematicians meet at an international conference and discover that among any three of them, at least two speak a common language. If each of the mathematicians speak at most three languages, prove that there are at least three of the mathematicians who can speak the same language.

For a quick view you will find it at google books. For a solution of the problem look here