There are 100 towns in some country and each two towns are connected by a one-way
road.
we are to Prove that one can change the direction of at most one road so that after that
each town will be reachable from any other one.
please help with the solution, thanks.
Best Answer
The towns and roads represent a tournament, a complete graph with every edge given a direction. Every tournament has a directed Hamiltonian path; if the end of that path is not already pointing to its start, simply flipping the edge between start and end will form a Hamiltonian cycle, whereupon all towns can be reached from all other towns by traversing the cycle.