Problem

Source: China Girls Math Olympiad 2019 Day 2 P4

Tags: combinatorics, graph theory



For a tournament with $8$ vertices, if from any vertex it is impossible to follow a route to return to itself, we call the graph a good graph. Otherwise, we call it a bad graph. Prove that $(1)$ there exists a tournament with $8$ vertices such that after changing the orientation of any at most $7$ edges of the tournament, the graph is always abad graph; $(2)$ for any tournament with $8$ vertices, one can change the orientation of at most $8$ edges of the tournament to get a good graph. (A tournament is a complete graph with directed edges.)