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
    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$ 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
    Aug 26, 2021 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.