Deleting cycle in a directed graph preserving connectivity
Source: Saint Petersburg 2017
August 18, 2017
combinatoricsgraph theoryRussiaPetersburg
Problem Statement
In a country, some pairs of cities are connected by one-way roads. It turns out that every city has at least two out-going and two in-coming roads assigned to it, and from every city one can travel to any other city by a sequence of roads. Prove that it is possible to delete a cyclic route so that it is still possible to travel from any city to any other city.