Taken from Problem 9-2 of MIT-ocw-course "Design and Analysis of Algorithms":
Define a tournament to be a directed graph $T = (V, E)$ such that, for every pair of distinct vertices $u, v \in V$, exactly one of $(u, v)$ and $(v, u)$ is in $E$. Furthermore, define a cycle cover to be a set $A \subset E$ of directed edges of a tournament such that, every directed cycle of $T$ contains at least one edge from $A$.
Problem (a) now says:
Let a minimal cycle cover of $T$ be a cycle cover with the least number of edges. Prove that reversing all the edges of a minimal cycle cover $A$ turns $T$ into an acyclic tournament. (Hint: Any edge $e \in A$ must be the only edge in $A$ on some directed cycle of $T$.)
My problem now is that my attempt at solving this problem is somehow different from what is presented in the solution. Here is my attempt:
Lemma 1:
Let T be a tournament graph.
If $A \subset E$ is a minimal cycle cover of $T$ $ \Rightarrow $ some edge $e \in A$ must be the only edge in $A$ on some directed cycle of $T$.
Proof of Lemma 1. By contradiction.:
Suppose, to the contrary, that if $A$ is a minimal cycle cover of $T$, then $e \in A$ is not the only edge in $A$ on some cycle $c$ of $T$. Call this other edge $f$.
But then, by the definition of a minimal cycle cover, we could simply remove $f$ from $A$ s.t. $A' = A \setminus f$ and $c$ would still be covered. But then we would obtain a smaller set $A'$. This is a contradiction since we assumed $A$ to be a minimal cycle cover. Hence, the Lemma must be true.
Proof of (a):
Let $A$ be a minimal cycle cover of $T$.
By Lemma 1 any edge $e \in A$ is the only edge in $A$ on some cycle of $T$. Reversing a single edge in a directed cycle breaks the cycle. Reversing every edge in $A$ reverses the only edge of the cycle which is in $A$ and therefore every cycle gets broken. Hence, the tournament $T$ is now acyclic which proves the claim.
This is the solution provided by the course:
Solution: Let $T ′$ be the new tournament. Suppose for contradiction that $T ′$ contains a cycle $C$. Let $F′$ be the set of edges of $C$ that were obtained by reversing the edges of $A$, and let $F$ be their reversals, which are edges in $T$. For each $e \in F$, let $C_e$ be a directed cycle of $T$ that $e$ covers. From the hint, we know $e$ is the only edge in $A$ that is also in $C_e$. Now we can construct a cycle $C′$ in $T$, consisting entirely of edges of $T$ that did not get reversed: Include all reverse of edges in $C \setminus F'$ (which are valid edges in $T$ ), and for each $e \in C \cap F′$, include all the edges of $C_e$ except for $e$. This yields a cycle $C′$ in $T$ that contains no edges in $A$, which is a contradiction.
My questions are now:
- Is my proof attempt correct?
- What is the reasoning behind the set $F'$? Do they mean all the edges of the cycle $C$ or just the reversed edges in $A$? I'm having a hard time to understand the reasoning behind the proof since I'm not quite sure what $F'$ should be.
For your lemma proof, your other edge $f$ might be part of another cycle, and removing it would mean there is no edge from $A$ in that cycle. Be careful also, that you want to show that any edge in $A$ must be the only edge in $A$ in some, not all, directed cycles.
For your main proof, it is true that the cycles get broken, but might new cycles be created?
The set $F'$ includes only the edges of $C$ that are reversed in $A$, not all edges of $C$.