Tournament strongly connected and arc reversal

directed graphsgraph theorygraph-connectivity

I'm working on Ádám's conjecture about arc reversal problem on digraphs with at least one cycle. The thing is that Reid proved in 1984 the following theorem:

Suppose that $T$ is a strongly connected tournament such that the reversal of any single arc results in a strongly connected tournament, but that the reversal of some pair of arcs results in a tournament that is not strongly connected. Then there exists an arc on $T$ such that the reversal of this arc results in a tournament with strictly fewer directed cycles than $T$.

In order to prove this, he said that for existing such a tournament there must be a non-empty subset $S$ of $V(T)$ such that the number of arcs directed from $S$ to $V(T)-S$ is exactly two. I'm stuck on this part. It is easy to see that there should be at least two arcs of this type, but I can't see why couldn't be three.

Any kind of help will be appreciated.

Best Answer

Let $T$ be a tournament in which reversing arcs $a$ and $b$ results in a tournament that's not strongly connected. Let $T^a$, $T^b$, and $T^{ab}$ be the tournaments with arc $a$, arc $b$, and both arcs reversed, respectively.

In order for $T^{ab}$ not to be strongly connected, there must be a set $S \subseteq V(T)$ such that $T^{ab}$ has no arcs directed from $S$ to $V(T) - S$.

Meanwhile, $T^a$ and $T^b$ are both strongly connected, so in particular they must each have a way to get from $S$ to $V(T)-S$. The only option that $T^a$ has that $T^{ab}$ does not is arc $b$: so arc $b$ must be directed from $S$ to $V(T)-S$ in $T^a$ (and in $T$). Similarly, the only option that $T^b$ has that $T^{ab}$ does not is arc $a$: so arc $a$ must be directed from $S$ to $V(T)-S$ in $T^b$ (and in $T$).

Therefore in $T$, there are exactly two arcs directed from $S$ to $V(T)-S$: arcs $a$ and $b$.