MathDB

(I'll skip over the whole "dressing" of the graph in cities and flights [color=#FF0000][Mod edit: Shu has posted the "dressed-up" version below])
For an ordinary directed graph, show that there is a subset A of vertices such that:

1.

There are no edges between the vertices of A.

2.

For any vertex

v

, there is either a direct way from

v

to a vertex in A, or a way passing through only one vertex and ending in A (like

v

v'

a

, where

a

is a vertex in A)

Problem Statement