1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I think I already solved it. If we suppose that for every bipartition of $V(T)$ there are three arcs going in each of both directions, then particulary it satisfies when one of the partitions is a single vertex, hence in $T$ every vertex has indegree and outdegree at least three. Reversing exactly two arcs results in a tournament where every vertex has indegree and outdegree at least one, hence the resultant tournament is strongly connected. Am I right? $\endgroup$
    – PAB
    Commented Aug 25, 2021 at 18:56
  • $\begingroup$ Just because every vertex has indegree and outdegree at least one doesn't mean that a tournament is strongly connected. $\endgroup$ Commented Aug 25, 2021 at 22:53

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Thanks a lot! I made a mistake on my previous answer, I was thinking about the existence of a directed cycle, I had a lapsus. $\endgroup$
    – PAB
    Commented Aug 26, 2021 at 1:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .