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.)
Problem
Source: China Girls Math Olympiad 2019 Day 2 P4
Tags: combinatorics, graph theory
13.08.2019 22:07
Nice problem! Solution with ewan. We enlist the help of Robitaille the Remover. Note that "good" just means "acyclic." Furthermore, it clearly suffices to show (in the case of (2)) that Robitaille can remove $8$ edges to make the graph acyclic; whereas in (1), we wish to show that Robitaille cannot necessarily win by removing 7 edges. This is because if removing some edges makes the graph acyclic, so does reorienting them (i.e. orienting them in the ``right" direction). (1) Connect $i\to i+1$, $i\to i+2$, $i+3\to i$; here, indices are mod $8$. Then, for each $i$, we have the directed cycle $i\to i+1\to i+3\to i$. These are disjoint, so Robitaille must remove an edge from each; thus 8 edges are necessary. (2) To show that Robitaille can always remove 8 edges to make the graph acyclic, we first show that if we have a tournament $T$ with $4$ vertices, then Robitaille can remove an edge to make $T$ acyclic. Indeed, note that if $T$ is already acyclic, then Robitaille is immediately done. Otherwise, there is always a triangle: If $abcd$ is a cycle then one of $ac, ca$ is an edge and this either gives us the $acd$ or $abc$ cycle. Without loss of generality say that there is an $abc$ cycle, and that $d$ is the last vertex. If $d$ has outdegree $0$ or $3$, then deleting $ab$ suffices. If $d$ has outdegree $1$, then assume without loss of generality that $da$ is the out-edge, and $bd, cd$ are in-edges. Then deleting $ab$ works; on the other hand if $ad$ is an in-edge while $db, dc$ are out, then deleting $ca$ works. Thus any tournament with four vertices can be made acyclic by deleting one edge. To finish from here, Robitaille can use divide and conquer. Let $V_1, \ldots, V_8$ be the vertices so that $V_i$ has outdegree $a_i$, and $a_1 \geq a_2 \geq \cdots \geq a_8$. First we claim that $a_1 + a_2 + a_3 + a_4 \geq 16$. This is clear, since if $a_4 \geq 4$ we are done, and otherwise $3\geq a_4\geq a_5$, so \[ 28 - (a_1 + a_2 + a_3 + a_4) = a_5 + a_6 + a_7 + a_8 \leq 12. \]Let $A = \{V_1, V_2, V_3, V_4\}$ and $B = \{V_5, V_6, V_7, V_8\}$, then we see that there are $a_1+a_2+a_3+a_4 - \binom 42\geq 10$ edges going from $A$ to $B$. Now, suppose Robitaille deletes all the edges going from $B$ to $A$, and then make $A, B$ each acyclic. Then, any cycle must use vertices from both $A$ and $B$ which is impossible as there are no edges going from $B$ to $A$. Thus after deleting the (at most $6$) edges from $B$ to $A$, and deleting at most one edge from $A, B$ to $A, B$ each acyclic, Robitaille has made the entire graph acyclic in at most $8$ deletions. $\blacksquare$
13.03.2020 04:58
Just as a note, I did not read Mathstudent2002's solution yet because I am currently trying to figure this out. I am currently having trouble dealing with the following construction of the problem for part $b$. Construct a tournament $G$ on 8 vertices and label its vertices $v_0, v_1, \cdots, v_7$. Consider the complete subgraph $G'$ of $G$ on the 7 vertices $v_0, v_1, \cdots, v_6$ which follow the following criteria where $v_i \rightarrow v_j$ for $i \neq j$ means we have a directed edge from $v_i$ to $v_j$ on $G'$: $$v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4 \rightarrow v_5 \rightarrow v_6 \rightarrow v_0 $$$$v_0 \rightarrow v_2 \rightarrow v_4 \rightarrow v_6 \rightarrow v_1 \rightarrow v_3 \rightarrow v_5 \rightarrow v_0 $$$$v_0 \rightarrow v_4 \rightarrow v_1 \rightarrow v_5 \rightarrow v_2 \rightarrow v_6 \rightarrow v_3 \rightarrow v_0 $$ I tried to reorient $8$ of the edges from $G'$ first so that the new graph is acyclic, but cannot see how this can be done. If I can get help on this smaller problem, that would be great.
19.11.2021 17:01
It is the only way to makw a GOOD graph.