MathDB

Some

n \geq 3

cities are connected with railways, so that you can travel from one city to every other, not necessarily directly. However, the railways are structured in such a way that there is only one way to get from one city to another, assuming you don't pass through the same city again. Let

A

be the set of these cities and railways. Show that there exists a Subset of

A

, let's say

C

, such that
(1)

C

has at least

[(n+1)/2]

cities as its element.
(2) No two elements of

C

are directly connected with railways.

Problem Statement