Problem #WSP-000151

Problems Graph theory

Problem

In the Kingdom of Rabbitland some cities are connected with each other by a railroad. There are two ways of getting from Longears city to Pufftown, one of them passes through an even number of other cities, and the other passes through an odd number of other cities. Show that in the Kingdom of Rabbitland there is a cycle of an odd number of distinct cities, such that each is connected to the next by railroads, and the last one is connected to the first one by railroads.