# On $d$-panconnected tournaments with large semidegrees

###### Abstract

We prove the following new results.

(a) Let $T$ be a regular tournament of order $2n+1\geq 11$ and $S$ a subset of
$V(T)$. Suppose that $|S|\leq\frac{1}{2}(n-2)$ and $x$, $y$ are distinct
vertices in $V(T)\setminus S$. If the subtournament $T-S$ contains an
$(x,y)$-path of length $r$, where $3\leq r\leq|V(T)\setminus S|-2$, then $T-S$
also contains an $(x,y)$-path of length $r+1$.

(b) Let $T$ be an $m$-irregular tournament of order $p$, i.e.,
$|d^{+}(x)-d^{-}(x)|\leq m$ for every vertex $x$ of $T.$ If
$m\leq\frac{1}{3}(p-5)$ (respectively, $m\leq\frac{1}{5}(p-3)$), then for
every pair of vertices $x$ and $y$, $T$ has an $(x,y)$-path of any length $k$,
$4\leq k\leq p-1$ (respectively, $3\leq k\leq p-1$ or $T$ belongs to a family
$\cal G$ of tournaments, which is defined in the paper). In other words, (b)
means that if the semidegrees of every vertex of a tournament $T$ of order $p$
are between $\frac{1}{3}(p+1)$ and $\frac{2}{3}(p-2)$ (respectively, between
$\frac{1}{5}(2p-1)$ and $\frac{1}{5}(3p-4)$), then the claims in (b) hold.

Our results improve in a sense related results of Alspach (1967), Jacobsen
(1972), Alspach et al. (1974), Thomassen (1978) and Darbinyan (1977, 1978,
1979), and are sharp in a sense.

Keywords: tournaments; arc pancyclicity; irregularity; paths; panconnected
tournaments; oudegree; indegree.

Samvel Kh. Darbinyan

Institute for Informatics and Automation Problems of NAS RA

Gregory Z. Gutin

Department of Compute Science, Royal Holloway, University of London, UK

E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>
##  1 Introduction

In this paper, we consider finite digraphs (directed graphs) without loops and
multiple arcs. We use standard notation and terminology, cf. [3] and [4]. The
vertex set and the arc set of a digraph $D$ are denoted by $V(D)$ and $A(D)$,
respectively. The order of $D$ is the number of its vertices. A subdigraph of
$D$ induced by a subset $A\subseteq V(D)$ is denoted by $D\langle A\rangle$.
If $X\subseteq V(D)$, then $D-X$ is the subdigraph induced by $V(D)\setminus
X$, i.e., $D-X=D\langle V(D)\setminus X\rangle$. Every cycle and path are
assumed to be simple and directed. Let $m$ and $n$, $m\leq n$, are integers.
By $[m,n]$ we denote the set $\\{m,m+1,\ldots,n\\}$.

A digraph $D$ of order $p$ is arc pancyclic (respectively, $d$-arc pancyclic,
where $d\in[3,p]$) if $D$ has a $k$-cycle containing $uv$ for every arc $uv\in
A(D)$ and every $k\in[3,p]$ (respectively, $k\in[d,p]$). We say that a digraph
$D$ of order $p$ is strongly panconnected (respectively, $d$-strongly
panconnected, where $d\in[3,p-1]$) if there is an $(x,y)$\- and a $(y,x)$-path
in $D$, both of length $k$, for any two vertices $x$, $y$ of $D$ and each
$k\in[3,p-1]$ (respectively, $k\in[d,p-1]$).

An oriented graph is a digraph with no cycle of length two. A tournament is an
oriented graph where every pair of distinct vertices are adjacent. The
outdegree $d^{+}(x)$ (respectively, indegree $d^{-}(x)$) of a vertex $x$ of a
digraph $D$ is the number of vertices $y$ such that $xy\in A(D)$
(respectively, $yx\in A(D)$). The irregularity $i(T)$ of a tournament $T$ is
the maximum of $|d^{+}(x)-d^{-}(x)|$ over all vertices $x$ of $T$. If
$i(T)=0$, then $T$ is regular and if $i(T)=1$, then $T$ is almost regular. If
$i(T)=m$, $T$ is $m$-irregular. Observe that every vertex of a tournament $T$
of order $p$ has outdegree between $\frac{1}{2}(p-1-i(T))$ and
$\frac{1}{2}(p-1+i(T))$. The outdegree and indegree of $x$ are its
semidegrees. Further digraph terminology and notation are given in the next
section.

There are a number of conditions which guarantee that a tournament is arc
pancyclic or strongly panconnected (see, e.g., [1]-[18]). In particular,
Alspach [1] proved that every regular tournament is arc pancyclic. Jacobsen
[12] proved that every almost regular tournaments of order $p\geq 8$ is 4-arc
pancyclic. Alspach et al. [2] proved that every regular tournament of order
$p\geq 7$ is strongly panconnected. Darbinyan [9] proved that every almost
regular tournament of order $p\geq 10$ is strongly panconnected.

Thomassen [17] generalized these results as follows:

######  Theorem 1.1.

Let $T$ be an $m$-irregular tournament of order $p$. If
$m\leq\frac{1}{5}(p-9)$, then $T$ is strongly panconnected. If
$m\leq\frac{1}{5}(p-3)$, then $T$ is 4-arc pancyclic.

In [8] and [10], Darbinyan obtained the following:

######  Theorem 1.2.

Let $T$ be a regular tournament of order $2n+1$ and let $S\subset V(T)$.

(i) [8] If $2\leq|S|\leq\frac{1}{3}(n-2)$, then $T-S$ is strongly
panconnected.

(ii) [10] Let $|S|\leq\frac{1}{2}(n-3)$ and $x,y\in V(T)\setminus S$ be two
distinct vertices. If $T-S$ contains an $(x,y)$-path of length $r$, where
$r\in[3,2n-|S|-1]$, then $T-S$ also contains an $(x,y)$-path of length $r+1$.

We will use the following result of Moon [14].

######  Theorem 1.3.

Let $H$ be an $m$-irregular tournament of order $p\geq 2$. Then there is a
regular tournament of order $p+m$ such that $T$ contains $H$ as a
subtournament.

From Theorems 1.2(ii) and 1.3 it is not difficult to obtain the following:

######  Corollary 1.4.

[10] Let $T$ be an $m$-irregular tournament of order $p\geq 7$, where
$m\leq\frac{1}{3}(p-7)$, and $x$, $y$ are two distinct vertices. If $T$
contains an $(x,y)$-path of length $r$, where $r\in[3,p-2]$, then $T$ also
contains an $(x,y)$-path of length $r+1$.

In this paper, we prove the following theorems, which improve in a sense the
above-mentioned results of Alspach, Jacobsen, Alspach et al., Thomassen and
Darbinyan. The following theorem is our main result.

######  Theorem 1.5.

Let $T$ be a regular tournament of order $2n+1\geq 11$ and let $S$ be a subset
in $V(T)$. Suppose that $|S|\leq\frac{1}{2}(n-2)$ and $x,y$ be two distinct
vertices in $V(T)\setminus S$. If $T-S$ contains an $(x,y)$-path of length
$r$, where $r\in[3,2n-|S|-1]$, then $T-S$ also contains an $(x,y)$-path of
length $r+1$.

Note that Theorem 1.2(i) was only announced in [8] and its proof has never
been published. The preprint [10] gave only an outline of the proof of Theorem
1.2(ii) and its complete proof has never been published either. Also note that
the main arguments in the proof of Theorem 1.5 are different from those in the
proof of Theorem 1.1 by Thomassen.

Remark 1 Let $H$ be a tournament of order $p\geq 5$ with irregularity
$m\leq\frac{1}{3}(p-5)$. Then by Theorem 1.3, there is a regular tournament
$T$ of order $p+m=2n+1$ such that $T$ contains $H$ as a subtournament. Let
$S=V(T)\setminus V(H)$. Note that $|S|=m$. Then we have
$p+\frac{1}{3}(p-5)\geq 2n+1$ implying $p\geq\frac{1}{2}(3n+4)$. Therefore,
$m=2n+1-p\leq 2n+1-\frac{1}{2}(3n+4)=\frac{1}{2}(n-2)$. Thus,
$|S|=m\leq\frac{1}{2}(n-2)$.

######  Theorem 1.6.

Let $T$ be an $m$-irregular tournament of order $p$ such that $p+m\geq 11$. If
$m\leq\frac{1}{3}(p-5)$ (respectively, $m\leq\frac{1}{5}(p-3)$), then $T$ is
4-strongly panconnected (respectively, $T$ is strongly panconnected or belongs
to the family $\cal G$ of tournaments defined in Section 3).

###### Proof.

Use the construction of Remark 1 to obtain a regular tournament $\hat{T}$
containing $T$. Let $2n+1=p+m$ be the order of $\hat{T}$. Let
$S=V(\hat{T})\setminus V(T).$

Let us first prove the case of $m\leq\frac{1}{3}(p-5)$. By Remark 1,
$m=|S|\leq\frac{1}{2}(n-2)$ and hence by Lemma 3.2(ii), $T$ has an
$(x,y)$-path of length 3 or 4 for every pair $x,y$ of distinct vertices. Also,
by Theorem 1.5, $T$ has an $(x,y)$-path of any length from 4 to $|V(T)|-1$.
Thus, $T$ is 4-strongly panconnected.

Now we prove the case of $m\leq\frac{1}{5}(p-3)$. Since $p+m\geq 11$ and
$m\leq\frac{1}{5}(p-3)$, we have $p\geq 10.$ Hence,
$m\leq\frac{1}{5}(p-3)\leq\frac{1}{3}(p-5)$ and we can use Lemma 3.2 to show
that $T$ either has an $(x,y)$-path of length 3 for every pair $x,y$ of
distinct vertices, or $T$ belongs to the family $\cal G$. If $T$ does not
belongs to $\cal G$, by Theorem 1.5, $T$ is strongly panconnected. ∎

Remark 2. Using the above observation, we can formulate Theorem 1.6 in terms
of semidegrees as follows: If the semidegrees of every vertex of a tournament
$T$ of order $p$ are between $\frac{1}{3}(p+1)$ and $\frac{2}{3}(p-2)$
(respectively, between $\frac{1}{5}(2p-1)$ and $\frac{1}{5}(3p-4)$), then the
assertion of Theorem 1.6 holds.

From Theorem 1.6 (Theorem 1.5) it follows that

(i) if $T$ is regular (i.e, $m=0$), then for $p\geq 11$ we have a result by
Alspach that any regular tournament is arc pancyclic (observe that any arc of
a regular tournament is on 3-cycle) and for $p\geq 11$ a result by Alspach et
al. that any regular tournament is strongly panconnected.

(ii) if $T$ is almost regular (i.e, $m=1$), then for $p\geq 10$ we have a
result by Jacobsen that any almost regular tournament is 4-arc pancyclic and a
result by Darbinyan that any almost regular tournament of order $p\geq 10$ is
strongly panconnected.

(iii) from Theorem 1.6 (Theorem 1.5) also we have Theorems 1.1 and 1.2.

The following remark shows that Theorem 1.5 is sharp in a sense.

Remark 3. If in Theorem 1.5 we replace $\frac{1}{2}(n-2)$ with
$\frac{1}{2}(n-1)$ (respectively, $\frac{n}{2}$), then there is a regular
tournament of order $2n+1=11$ (respectively, $2n+1=13$), which contains a
subset $S\subset V(T)$ with $|S|=\frac{1}{2}(n-1)$ (respectively,
$|S|=\frac{n}{2}$) and two distinct vertices $x,y\in V(T)\setminus S$ such
that $T-S$ contains an $(x,y)$-path of length 3, but $T-S$ contains no
$(x,y)$-path of length 4.

Here we define only a regular tournament $T$ of order $2n+1=11$ as follows:

$V(T)=\\{x_{0},x_{1},x_{2},x_{3}\\}\cup A\cup S$, where
$A=\\{u_{1},u_{2},u_{3},u_{4},z\\}$ and $S=\\{v_{1},v_{2}\\}$. The arc set of
$T$ is defined by in-neighborhoods of vertices as follows: $N^{-}(x_{0})=A$,
$N^{-}(x_{1})=\\{x_{0},z,u_{3},u_{4},v_{2}\\}$,
$N^{-}(x_{2})=\\{x_{0},x_{1},z,u_{3},u_{4}\\}$,
$N^{-}(x_{3})=\\{x_{0},x_{1},x_{2}\\}\cup S$,
$N^{-}(z)=\\{x_{3},u_{1},u_{2},u_{3},u_{4}\\}$,
$N^{-}(u_{1})=\\{x_{1},x_{2},x_{3},u_{4},v_{2}\\}$,
$N^{-}(u_{2})=\\{x_{1},x_{2},x_{3},u_{1},v_{1}\\}$,
$N^{-}(u_{3})=\\{x_{3},u_{1},u_{2},v_{1},v_{2}\\}$,
$N^{-}(u_{4})=\\{x_{3},u_{2},u_{3},v_{1},v_{2}\\}$,
$N^{-}(v_{1})=\\{x_{0},x_{1},x_{2},z,u_{1}\\}$ and
$N^{-}(v_{2})=\\{x_{0},x_{2},z,v_{1},u_{2}\\}$.

It is not difficult to check that $T$ contains an $(x_{0},x_{3})$-path of
length 3, but contains no $(x_{0},x_{3})$-path of length 4.

##  2 Further terminology and notation

If $xy$ is an arc of a digraph $D$, then we say that $x$ dominates $y$. For
disjoint subsets $B$ and $C$ of $V(D)$, let $A(B\rightarrow C)=\\{xy\in
A(D)\,|\,x\in B,y\in C\\}$. We write $B\rightarrow C$ if every vertex of $B$
dominates every vertex of $C$. If $A\subseteq V(D)\setminus(B\cup C)$, then
$A\rightarrow B\rightarrow C$ is a shortcut for $A\rightarrow B$ and
$B\rightarrow C$. If $x\in V(D)$ and $A=\\{x\\}$, we write $x$ instead of
$\\{x\\}$.

The out-neighborhood (respectively, in-neighborhood) of a vertex $x$ is the
set $N^{+}(x)=\\{y\in V(D)\,|\,xy\in A(D)\\}$ (respectively, $N^{-}(x)=\\{y\in
V(D)\,|\,yx\in A(D)\\}$). Similarly, if $B\subseteq V(D)$, then
$N^{+}(x,B)=\\{y\in B\,|\,xy\in A(D)\\}$ and $N^{-}(x,B)=\\{y\in B\,|\,yx\in
A(D)\\}$. We define $N^{+2}(x,B)$ and $N^{-2}(x,B)$ as follows:

$N^{+2}(x,B)=\\{z\in B\setminus(\\{x\\}\cup N^{+}(x,B))\,\,|\,\,yz\in
A(D),y\in N^{+}(x,B)\\},$ $N^{-2}(x,B)=\\{z\in B\setminus(\\{x\\}\cup
N^{-}(x,B))\,\,|\,\,zy\in A(D),y\in N^{-}(x,B)\\}.$

Note that for a vertex $x$, we have $d^{+}(x)=|N^{+}(x)|$ and
$d^{-}(x)=|N^{-}(x)|$. Similarly, let $d^{+}(x,B)=|N^{+}(x,B)|$ and
$d^{-}(x,B)=|N^{-}(x,B)|$.

The path (respectively, the cycle) in $D$ consisting of distinct vertices
$x_{1},x_{2},\ldots,x_{m}$ ($m\geq 2$) and arcs $x_{i}x_{i+1}$, $i\in[1,m-1]$
(respectively, $x_{i}x_{i+1}$, $i\in[1,m-1]$, and $x_{m}x_{1}$), is denoted by
$x_{1}x_{2}\cdots x_{m}$ (respectively, $x_{1}x_{2}\cdots x_{m}x_{1}$). The
length of a cycle or a path is the number of its arcs. A $k$-cycle is a cycle
of length $k$. We say that $x_{1}x_{2}\ldots x_{m}$ is a path from $x_{1}$ to
$x_{m}$ or is an $(x_{1},x_{m})$-path. The digraph $\overleftarrow{D}$
obtained from a digraph $D$ by replacing every arc $xy\in A(D)$ with the arc
$yx$ is called the converse of $D.$ We will use the principle of digraph
duality: Let $D$ be a digraph and $\overleftarrow{D}$ the converse of $D$.
Then $D$ contains a subdigraph $H$ if and only if $\overleftarrow{D}$ contains
the converse $\overleftarrow{H}$ of $H$.

##  3  Preliminaries

The following lemma states several well-known and simple claims which are the
basis of our results and other theorems on directed cycles and paths in
tournaments. The claims will be used extensively in the proof of our result.

######  Lemma 3.1.

Let $T$ be a tournament of order $p\geq 2$. Then the following statements are
true.

(i) The tournament $T$ contains two distinct vertices $x$ and $y$
(respectively, $u$ and $v$) such that $d^{-}(x)\leq\frac{1}{2}(p-1)$ and
$d^{-}(y)\geq\frac{1}{2}(p-1)$ (respectively, $d^{+}(u)\leq\frac{1}{2}(p-1)$
and $d^{+}(v)\geq\frac{1}{2}(p-1)$).

(ii) If $T$ is regular, then $p=2n+1$ and for any vertex $x\in V(T)$,
$d^{-}(x)=d^{+}(x)=n$.

(iii) If $T$ is not regular, then $T$ contains two distinct vertices $x$ and
$y$ (respectively, $u$ and $v$) such that $d^{-}(x)\leq\frac{1}{2}(p-2)$ and
$d^{-}(y)\geq\frac{1}{2}p$ (respectively, $d^{+}(u)\leq\frac{1}{2}(p-2)$ and
$d^{+}(v)\geq\frac{1}{2}p$.

(iv) If $T$ is almost regular, then $p=2n$ and $n$ vertices have indegrees
equal to $n$ and the other $n$ vertices have outdegrees equal to $n$.

(v) Let $T$ be a non-regular tournament. If for all $v\in V(T)$,
$d^{-}(v)<\frac{1}{2}(p+1)$ (or $d^{+}(v)<\frac{1}{2}(p+1)$), then $T$ is
almost regular.

(vi) Let $T$ be a tournament. If for all $v\in V(T)$, $d^{-}(v)<\frac{1}{2}p$
(or $d^{+}(v)<\frac{1}{2}p$), then $T$ is regular.

To formulate Lemma 3.2, we need the following definition.

Definition. By $\cal G$ we denote the set of regular tournaments, each of
which has order $6k+3\geq 9$ and vertex set $\\{x,y,z\\}\cup A\cup B\cup C\cup
S$ with the properties $|A|=|C|=2k-1$, $|B|=k+2$, $|S|=k$, the subtournaments
induced by the subsets $A$, $C$, $\\{z\\}\cup B\cup S$ are regular,
$A\rightarrow B\cup S\rightarrow C$, $C\rightarrow A$, $C\rightarrow
z\rightarrow A$, $x\rightarrow\\{y,z\\}\cup A\cup S$, $\\{x,z\\}\cup C\cup
S\rightarrow y$, $y\rightarrow A\cup B$ and $B\cup C\rightarrow x$.

Let $G\in\cal G$. Observe that $G-S$ has no $(x,y)$-path of length 3.

Remark 3. It is interesting that Thomassen [17] used tournaments of the form
$G-S,$ where $G\in\cal G$ to show that there are many tournaments of order $p$
with irregularity equal to $\frac{1}{5}(p-3)$, which are not 3-strongly
panconnected.

######  Lemma 3.2.

Let $T$ be a regular tournament of order $2n+1$. Suppose that $S\subseteq
V(T)$ and $x$, $y$ are two distinct vertices in $V(T)\setminus S$. Then the
following hold:

(i) If $n\geq 3$ and $k=|S|\leq\frac{1}{3}(n-1)$, then $T-S$ contains an
$(x,y)$-path of length 3, unless $T$ is isomorphic to a tournament from $\cal
G$.

(ii) If $n\geq 5$ and $k=|S|\leq\frac{1}{2}n$ and $T-S$ contains no
$(x,y)$-path of length 3, then $T-S$ contains an $(x,y)$-path of length 4.

###### Proof.

Let $A=V(T)\setminus(\\{x,y\\}\cup S)$ and $R=N^{+}(x,A)\cap N^{-}(y,A)$. If
$T-S$ contains no $(x,y)$-path of length 3, then $|R|\leq 1$,
$|A(N^{+}(x,A)|\geq n-k-1$ and

$A(N^{+}(x,A)\rightarrow N^{-}(y,A))=\emptyset,\quad\hbox{i.e.,}\quad
N^{-}(y,A)\rightarrow N^{+}(x,A)$ $None$

and observe that

$|N^{+}(x,A)\setminus R|\geq n-k-2\quad\hbox{and}\quad|N^{-}(y,A)\setminus
R|\geq n-k-2.$ $None$

(i) Suppose that $T-S$ contains no $(x,y)$-path of length 3. Note that
$T^{\prime}=T\langle N^{+}(x,A)\setminus R\rangle$ must contain a vertex $u$
with $d^{-}(u,T^{\prime})\geq(|V(T^{\prime})|-1)/2,$ the average indegree in
$T^{\prime}$. Using (1) and (2), we obtain that the following holds for
$d^{-}(u)$:

$n=d^{-}(u)\geq|\\{x,y\\}|+|N^{-}(y,A)|+(|N^{+}(x,A)\setminus R|-1)/2$ $\geq
n-k+1+(n-k-3)/2=n+(n-3k-1)/2.$ $None$

Therefore, $n-3k-1\leq 0$, i.e., $3k=n-1$ as $3k\leq n-1$, and all the
inequalities that led to (3) in fact are equalities. This means that
$|N^{+}(x,A)\setminus R|=n-k-2$ (by the digraph duality, $|N^{-}(y,A)\setminus
R|=n-k-2$), $|R|=1$, $|B|=k+2$, where $B=A\setminus(N^{+}(x,A)\cup
N^{-}(y,A))$, $y\rightarrow B\rightarrow x$, $x\rightarrow S\rightarrow y$,
$T\langle N^{+}(x,A)\setminus R\rangle$ is a regular tournament (by the
digraph duality, $T\langle N^{-}(y,A)\setminus R\rangle$ is also a regular
tournament), $N^{+}(x,A)\setminus R\rightarrow S\cup B\rightarrow
N^{-}(y,A)\setminus R$, $y\rightarrow N^{+}(y,A)\setminus R$,
$N^{-}(x,A)\setminus R\rightarrow x$, $xy\in A(T)$ and $T\langle S\cup B\cup
R\rangle$ is a regular tournament. Therefore, $T$ is isomorphic to a
tournament of the type $\cal G$.

(ii) By contradiction, suppose that $T-S$ contains no $(x,y)$-path of lengths
3 and 4. By Lemma 3.1, we know that there is a vertex $u\in
N^{+}(x,A)\setminus R$ such that $d^{+}(u,N^{+}(x,A)\setminus
R)\leq(|N^{+}(x,A)\setminus R|-1)/2$. Consider the out-neighbors of $u$. Since
$d^{+}(u)=n$ and $u$ can not dominate $x$ and $y$, the number of out-neighbors
of $u$ in $A$ is at least $n-k$. Further the out-neighbors of $u$ which are
contained in $N^{+}(x,A)\setminus R$ are all in $N^{+2}(x,A)$. This together
with (1) implies that

$|N^{+2}(x,A)|\geq n-k-(|N^{+}(x,A)\setminus
R|-1)/2=(2n-2k-|N^{+}(x,A)\setminus R|+1)/2.$

Since $T-S$ contains no $(x,y)$-path of length 4, it follows that
$N^{-}(y,A)\setminus R\rightarrow N^{+2}(x,A))$. This together with (1), (2)
and the last inequality implies that for some vertex $v\in N^{-}(y,A)\setminus
R$ the following holds

$d^{+}(v)\geq|\\{x,y\\}|+|N^{+}(x,A)|+(|N^{+2}(x,A)|+(|N^{-}(y,A)\setminus
R|-1)/2\geq 2n-2k+1.$

Hence, $2k\geq n+1$, which is a contradiction. This completes the proof of the
lemma.∎

For $n=3$ and $n=4$, it is not difficult to construct tournaments for which
Lemma 3.2(ii) is not true. To see this, we consider the following examples of
regular tournaments of order 7 and 9.

Let $T$ be a regular tournament of order 7 (of order 9) with vertex set
$V(T)=\\{x,y,z\\}\cup B\cup S$, where $|S|=1$, $|B|=3$ (respectively, $|S|=2$,
$|B|=4$). The tournament $T$ satisfies the following conditions:

$A(T)$ contains the arcs $xy$, $xz$ and $zy$, $x\rightarrow S\rightarrow y$,
$y\rightarrow B\rightarrow x$ and $T\langle\\{z\\}\cup B\cup S\rangle$ is a
regular tournament. It is easy to check that $|S|\leq n/2$ and $T-S$ contains
no $(x,y)$-path of lengths 3 and 4.

Note that if we in Lemma 3.2(ii), $\frac{1}{2}n$ replace with
$\frac{1}{2}(n+1)$, then there is a regular tournament $T$ of order $2n+1=11$
($2n+1=15$) which contains a subset $S\subseteq V(T)$ with
$|S|=k=\frac{1}{2}(n+1)$ and two distinct vertices $x,y\in V(T-S)$ such that
$T-S$ contains no path of lengths 3 and 4. To see this we define a regular
tournament $T$ of order $2n+1=11$ ($2n+1=15$) as follows:

(a) Let $T$ be a regular tournament of order 11 with $V(T)=\\{x,y,z\\}\cup
A\cup S$ such that $|A|=5$, $k=|S|=3$, $x\rightarrow S\rightarrow y$,
$y\rightarrow A\rightarrow x$, the arcs $xy,xz,zy$ are in $A(T)$ and
$T\langle\\{z\\}\cup A\cup S\rangle$ is a regular tournaments.

It is easy to check that $T-S$ contains no $(x,y)$-path of length greater or
equal to 3.

(b) Let $T$ be a regular tournament of order 15 with $V(T)=\\{x,y,z,u,v\\}\cup
A\cup B\cup S$ such that $|A|=|B|=3$, $k=|S|=4$,
$S=\\{a_{1},a_{2},b_{1},b_{2}\\}$, the arcs $xy,xz,zy,xu,vy,vu,vz,\\\
zu,a_{1}a_{2},b_{1}b_{2},a_{2}b_{2},a_{2}b_{1},a_{1}b_{1},b_{2}a_{1}$ are in
$A(T)$, $x\rightarrow S\rightarrow y$, $\\{y,z,u,v\\}\rightarrow A$,
$B\rightarrow\\{x,u,v,z\\}$, $y\rightarrow\\{u\\}\cup B$,
$A\rightarrow\\{x\\}\cup B$, $v\rightarrow\\{x\\}\cup A$, $S\rightarrow v$,
$u\rightarrow A\cup S$, the induced subtournaments $T\langle A\rangle$ and
$T\langle B\rangle$ are regular tournaments, $\\{b_{1},b_{2}\\}\rightarrow
A\rightarrow\\{a_{1},a_{2}\\}$, $\\{a_{1},a_{2}\\}\rightarrow
B\rightarrow\\{b_{1},b_{2}\\}$ and $\\{b_{1},b_{2}\\}\rightarrow
z\rightarrow\\{a_{1},a_{2}\\}$.

It is not difficult to check that $T-S$ contains no $(x,y)$-path of length 3
and 4. Note that $T-S$ contains an $(x,y)$-path of every length
$5,6,\ldots,10$.

In Lemmas 3.3 and 3.4, we suppose that $P:=x_{0}x_{1}\ldots x_{r}$ is an
$(x_{0},x_{r})$-path of length $r$ in a tournament $T$ and $z$ is a vertex in
$V(T)\setminus V(P)$ such that
$\\{x_{\alpha+1},x_{\alpha+2},\ldots,x_{r}\\}\rightarrow
z\rightarrow\\{x_{0},x_{1},\ldots,x_{\alpha}\\}$, where $\alpha\in[2,r-3]$.
Moreover, any $(x_{0},x_{r})$-path of length $r+1$ with vertex set
$\\{z\\}\cup V(P)$ is denoted by $Q,$ and we assume that $T$ contains no such
a path $Q$.

######  Lemma 3.3.

Suppose that $x_{s}x_{t}\in A(T)$ with $s\in[1,\alpha-1]$ and
$t\in[\alpha+3,r]$. Then
$A(\\{x_{0},x_{1},\ldots,x_{s-2}\\}\rightarrow\\{x_{\alpha+2},x_{\alpha+3},\ldots,x_{t-1}\\})=\emptyset$
when $s\geq 3$, and

$A(x_{s-1}\rightarrow\\{x_{\alpha+2},x_{\alpha+3},\ldots,x_{t-1}\\})=\emptyset,\quad
when\quad t-s\not=5.$

###### Proof.

By contradiction, suppose that there exist integers $a\in[0,s-1]$ and
$b\in[\alpha+2,t-1]$ such that $x_{a}x_{b}\in A(T)$. Observe that
$\\{x_{b-1},x_{t-2},x_{t-1}\\}\rightarrow
z\rightarrow\\{x_{a+1},x_{a+2},x_{s+1}\\}$. Note that $t-s\geq 4$. Now we
prove the following facts.

Fact 3.1. (i) $x_{a+1}x_{b-1}\in A(T)$.

(ii) If $a\leq s-2$, then $x_{s+1}x_{a+1}\in A(T)$ and if $a=s-1$, then
$x_{s+2}x_{s}\in A(T)$ and $t-s\geq 6$.

Proof. (i). Indeed, if $x_{b-1}x_{a+1}\in A(T)$, then $Q=x_{0}x_{1}\ldots
x_{a}x_{b}\ldots x_{t-1}zx_{s+1}\ldots x_{b-1}\\\ x_{a+1}\ldots
x_{s}x_{t}\ldots x_{r}$, a contradiction.

(ii). If $a\leq s-2$ and $x_{a+1}x_{s+1}\in A(T)$, then

$Q=x_{0}x_{1}\ldots x_{a+1}x_{s+1}\ldots x_{t-1}zx_{a+2}\ldots
x_{s}x_{t}\ldots x_{r}.$

If $a=s-1$ and $x_{s}x_{s+2}\in A(T)$. Then either $x_{s+1}x_{t-1}\in A(T)$
and

$Q=x_{0}x_{1}\ldots x_{s}x_{s+2}\ldots x_{t-2}zx_{s+1}x_{t-1}\ldots x_{r}$

or $x_{t-1}x_{s+1}\in A(T)$ and $Q=x_{0}\ldots x_{s-1}x_{b}\ldots
x_{t-1}x_{s+1}\ldots x_{b-1}zx_{s}x_{t}\ldots x_{r}$. Thus, in both cases we
have a contradiction.

It is easy to see that from $x_{s}x_{b-1}\in A(T)$ and $x_{s+2}x_{s}\in A(T)$
it follows that $b-1\geq s+3$ and hence, $t-s\geq 6$ since $t-s\not=5$ when
$a=s-1$.

Fact 3.2. If $x_{i}x_{a+1}\in A(T)$ with $i\in[s+1,b-3]$, then
$x_{i+2}x_{a+1}\in A(T)$.

Proof. To prove it by contradiction, suppose that $x_{i}x_{a+1}\in A(T)$ with
$i\in[s+1,b-3]$ and $x_{a+1}x_{i+2}\in A(T)$. If $x_{t-1}x_{i+1}\in A(T)$,
then

$Q=x_{0}x_{1}\ldots x_{a}x_{b}\ldots x_{t-1}x_{i+1}\ldots x_{b-1}\\\
zx_{s+1}\ldots x_{i}x_{a+1}\ldots x_{s}x_{t}\ldots x_{r},$

and if $x_{i+1}x_{t-1}\in A(T)$, then $Q=x_{0}x_{1}\ldots x_{a+1}x_{i+2}\ldots
x_{t-2}zx_{a+2}\ldots x_{i+1}x_{t-1}\ldots x_{r}$, a contradiction.

Using Fact 3.2, it is not difficult to see that there is no $i\in[s+1,b-3]$
such that $\\{x_{i},x_{i+1}\\}\rightarrow x_{a+1}$, i.e.,
$d^{-}(x_{a+1},\\{x_{i},x_{i+1}\\})\leq 1$ (for otherwise, we obtain that
$x_{b-1}x_{a+1}\in A(T)$, contradicting Fact 3.1 that $x_{a+1}x_{b-1}\in
A(T)$). By Fact 3.1 we have that if $a\leq s-2$, then $x_{s+1}x_{a+1}\in
A(T)$, and $a=s-1$, then $x_{s+2}x_{s}\in A(T)$. This together with
$d^{-}(x_{a+1},\\{x_{i},x_{i+1}\\})\leq 1$ and Fact 3.2 implies that

$\hbox{if}\,\,a\leq
s-2,\,\,\hbox{then}\,\,\\{x_{s+1},x_{s+3},\ldots,x_{b-2}\\}\rightarrow
x_{a+1}\rightarrow\\{x_{s+2},x_{s+4},\ldots,x_{b-1}\\},$
$\hbox{if}\,\,a=s-1,\,\,\hbox{then}\,\,\\{x_{s+2},x_{s+4},\ldots,x_{b-2}\\}\rightarrow
x_{s}\rightarrow\\{x_{s+1},x_{s+3},\ldots,x_{b-1}\\}.$ $None$

Thus, in both cases we have $x_{b-2}x_{a+1}\in A(T)$. Now using (4), we
obtain, if $x_{t-1}x_{b-1}\in A(T)$, then $b\leq t-2$ and $Q=x_{0}\ldots
x_{a}x_{b}\ldots x_{t-1}x_{b-1}zx_{s+1}\ldots x_{b-2}x_{a+1}\ldots
x_{s}x_{t}\ldots x_{r}$, and if $b\leq t-2$ and $x_{b-1}x_{t-1}\in A(T)$, then
$Q=x_{0}\ldots x_{a}x_{b}\ldots x_{t-2}zx_{a+1}\ldots x_{b-1}x_{t-1}\ldots
x_{r}$, thus in both cases we have a contradiction. We may therefore assume
that $b=t-1$. In this case, if $x_{b}x_{s+1}\in A(T)$, then
$Q=x_{0}x_{1}\ldots x_{a}x_{b}x_{s+1}\ldots x_{b-1}zx_{a+1}\ldots
x_{s}x_{t}\ldots x_{r}$, a contradiction. Therefore, we may assume that
$x_{s+1}x_{b}\in A(T)$. This follows that if $a\leq s-2$, then $Q=x_{0}\ldots
x_{a+1}x_{s+2}\ldots x_{b-1}zx_{a+2}\ldots x_{s+1}x_{b}\ldots x_{r}$, a
contradiction. Assume that $a=s-1$. Then by Fact 3.1(ii), $t-s\geq 6$. Let
$t\geq\alpha+4$. It is easy to see that if $x_{b-1}x_{s+2}\in A(T)$, then by
(4), $x_{a+1}x_{s+2}\in A(T)$ and $Q=x_{0}x_{1}\ldots
x_{s}x_{b-1}x_{s+2}\ldots x_{b-2}zx_{s+1}x_{b}\ldots x_{r}$, and if
$x_{s+2}x_{b-1}\in A(T)$, then $Q=x_{0}x_{1}\ldots x_{s}x_{s+3}\ldots
x_{b-2}zx_{s+1}x_{s+2}x_{b-1}\ldots x_{r}$. Let now $t=\alpha+3$. Then
$b=\alpha+2$ and $z\rightarrow\\{x_{s+1},x_{s+2},\ldots,x_{\alpha}\\}$. From
$t-s\geq 6$ and (4) it follows that $t-s\geq 7$ and $\alpha\geq s+4$. From (4)
we also have that $x_{b-4}x_{s}\in A(T)$. Therefore, if $x_{b}x_{b-3}\in
A(T)$, then $Q=x_{0}x_{1}\ldots
x_{s-1}x_{b}x_{b-3}x_{b-2}x_{b-1}zx_{s+1}\ldots x_{b-4}x_{s}x_{t}\ldots
x_{r}$, a contradiction. We may therefore assume that $x_{b-3}x_{b}\in A(T)$.
If $x_{b-2}x_{s+1}\in A(T)$, then $Q=x_{0}x_{1}\ldots
x_{s}x_{b-1}zx_{b-2}x_{s+1}\ldots x_{b-3}x_{b}\ldots x_{r}$, a contradiction.
Thus, we have that $x_{b-3}x_{b}\in A(T)$ and $x_{s+1}x_{b-2}\in A(T)$.
Therefore, $Q=x_{0}x_{1}\ldots x_{s+1}x_{b-2}x_{b-1}zx_{s+2}\ldots
x_{b-3}x_{b}\ldots x_{r}$, a contradiction. Thus, in all cases we have a
contradiction. ∎

######  Lemma 3.4.

Suppose that $x_{s}x_{t}\in A(T)$ with $s\in[\alpha,r-2]$ and $t\in[s+2,r]$.
If $k=\lfloor\frac{1}{2}(t-s)\rfloor$, then
$A(\\{x_{0},x_{1},\ldots,x_{\alpha-1}\\}\rightarrow\\{x_{s+1},x_{s+2},\ldots,x_{s+k}\\})=\emptyset$.

###### Proof.

The proof by induction on $k=\lfloor\frac{1}{2}(t-s)\rfloor$. Observe that
$\\{x_{s+1},x_{t-1}\\}\rightarrow z$. For the base step, it is easy to see
that if $x_{i}x_{s+1}\in A(T)$ with $i\in[0,\alpha-1]$, then
$Q=x_{0}x_{1}\ldots x_{i}x_{s+1}\ldots x_{t-1}zx_{i+1}\ldots x_{s}x_{t}\ldots
x_{r}$, a contradiction. We may therefore assume that
$A(\\{x_{0},x_{1},\ldots,x_{\alpha-1}\\}\rightarrow x_{s+1})=\emptyset$. This
means that if $2\leq t-s\leq 3$, then the lemma is true. Assume that $t-s\geq
4$. For the inductive step, we assume that if $x_{s_{1}}x_{t_{1}}\in A(T)$
with $s_{1}\in[\alpha,r-2]$, $t_{1}\in[s_{1}+2,r]$ and $t_{1}-s_{1}<t-s$, then
$A(\\{x_{0},x_{1},\ldots,x_{\alpha-1}\\}\rightarrow\\{x_{s_{1}+1},x_{s_{1}+2},\ldots,x_{s_{1}+k_{1}}\\})=\emptyset$,
where $k_{1}=\lfloor\frac{1}{2}(t_{1}-s_{1})\rfloor$.

If $x_{t-1}x_{s+1}\in A(T)$, then for all $i\in[1,\alpha-1]$ and
$j\in[s+2,t-1]$, $x_{i}x_{j}\notin A(T)$ and we are done (for otherwise, if
$x_{i}x_{j}\in A(T)$, then $Q=x_{0}x_{1}\ldots x_{i}x_{j}\ldots
x_{t-1}x_{s+1}\ldots x_{j-1}z\\\ x_{i+1}\ldots x_{s}x_{t}\ldots x_{r}$, a
contradiction). Therefore,
$A(\\{x_{0},x_{1},\ldots,x_{\alpha-1}\rightarrow\\{x_{s+1},x_{s+2},\ldots,\\\
x_{t-1}\\})=\emptyset$ and we are done. Now assume that $x_{s+1}x_{t-1}\in
A(T)$. Then $t-1-(s+1)<t-s$ and, by the induction hypothesis,
$A(\\{x_{0},x_{1},\ldots,x_{\alpha-1}\\}\rightarrow\\{x_{s+2},\ldots,x_{s+1+m}\\})=\emptyset$,
where $m=\lfloor(t-s-2)/2\rfloor$. Thus,
$A(\\{x_{0},x_{1},\ldots,x_{\alpha-1}\\}\rightarrow\\{x_{s+1},x_{s+2},\ldots,x_{s+1+m}\\})=\emptyset$.
This implies that Lemma 3.4 is true since
$m+1=\lfloor\frac{1}{2}(t-s)\rfloor$. ∎

##  4 Proof of the main result

For convenience of the reader, we restate it here.

Theorem 1.5. Let $T$ be a regular tournament of order $2n+1\geq 11$ and let
$S$ be a subset in $V(T)$. Let $|S|\leq\frac{1}{2}(n-2)$ and $x,y$ be two
distinct vertices in $V(T)\setminus S$. If $T-S$ contains an $(x,y)$-path of
length $r$, where $r\in[3,2n-|S|-1]$, then $T-S$ also contains an $(x,y)$-path
of length $r+1$.

###### Proof.

Recall that $P=x_{0}x_{1}\dots x_{r}$ is a path of length $r$ in $T$ and
$k=|S|.$

Observe that for any vertex $x\in V(T-S)$, $d^{-}(x,V(T-S))\geq n-k$ and
$d^{+}(x,V(T-S))\geq n-k$. Now by $Q$ we denote any $(x_{0},x_{r})$-path of
length $r+1$ in $T-S$. Suppose that $T-S$ has no such path $Q$. Let
$A=V(T)\setminus(V(P)\cup S)$. We will prove a series of claims (Claims 1-13).

Claim 1: $N^{-}(x_{r},A)=N^{+}(x_{0},A)=\emptyset$, i.e.,
$d^{-}(x_{r},A)=d^{+}(x_{0},A)=0$.

Proof: By the digraph duality, it suffices to prove that
$N^{-}(x_{r},A)=\emptyset$. Suppose, on the contrary, that
$N^{-}(x_{r},A)\not=\emptyset$. Let $z\in N^{-}(x_{r},A)$, i.e., $zx_{r}\in
A(T)$. Then $z\rightarrow\\{x_{0},x_{1},\ldots,x_{r}\\}$, $r\leq n-1$ and
$|N^{-}(z,A)|\geq n-k$. It is easy to see that

$A(\\{x_{0},x_{1},\ldots,x_{r-2}\\}\rightarrow
N^{-}(z,A)\cup\\{z\\})=\emptyset.$ $None$

We distinguish the following two cases depending on $r$.

Case 1.1. $r\geq n-k$. We know that $N^{-}(z,A)$ contains a vertex $u$ such
that $d^{-}(u,N^{-}(z,A))\leq 0.5(d^{-}(z,A)-1)$. This together with (5)
implies that

$|N^{-2}(z,A)|\geq|N^{-2}(z,A)\cap N^{-}(u)|\geq n-k-2-0.5(d^{-}(z,A)-1).$
$None$

It is easy to see that $A(\\{x_{0},x_{1},\ldots,x_{r-3}\\}\rightarrow
N^{-2}(z,A))=\emptyset$. This together with (5) implies that $\\{z\\}\cup
N^{-}(z,A)\cup N^{-2}(z,A)\rightarrow\\{x_{0},x_{1},\ldots,x_{r-3}\\}$.
Therefore, $\\{x_{0},x_{1},\ldots,x_{r-3}\\}$ contains a vertex $v$ such that
$d^{-}(v)\geq|N^{-}(z,A)|+|N^{-2}(z,A)|+1+0.5(r-3)$ and unless
$\\{x_{0},x_{1},\dots,x_{r-3}\\}$ induces a regular tournament, we can find a
vertex $v$ so that equality does not hold. Now using (6), $r\geq n-k$ and the
fact that $|N^{-}(z,A)|\geq n-k$, we obtain

$n=d^{-}(v)\geq d^{-}(z,A)+n-k-2-0.5(d^{-}(z,A)-1)+0.5(r-1)\geq 2n-2k-2.$

Therefore, $2k=n-2$ (as $2k\leq n-2$) and all inequalities which were used in
the last inequality in fact are equalities, in particular,
$T\langle\\{x_{0},x_{1},\ldots,x_{r-3}\\}\rangle$ is a regular tournament.
Therefore, $\\{x_{0},x_{1},\ldots,x_{r-3}\\}\rightarrow x_{r-2}$. Hence,

$\displaystyle d^{-}(x_{r-2})$ $\displaystyle\geq$
$\displaystyle|N^{-}(z,A)|+|\\{z\\}|+|\\{x_{0},x_{1},\ldots,x_{r-3}\\}|$
$\displaystyle\geq$ $\displaystyle n-k+1+r-2$ $\displaystyle\geq$
$\displaystyle n-k+1+n-k-2$ $\displaystyle=$ $\displaystyle 2n-2k-1$
$\displaystyle\geq$ $\displaystyle 2n-(n-2)-1$ $\displaystyle=$ $\displaystyle
n+1,$

a contradiction.

Case 1.2. $r\leq n-k-1$. Then $N^{+}(x_{0},A)\not=\emptyset$. It is easy to
see that

$N^{+}(x_{0},A)\cap N^{-}(z,A)=A(N^{+}(x_{0},A)\rightarrow
N^{-}(z,A)\cup\\{z,x_{1},x_{2},\ldots,x_{r}\\})=\emptyset.$ $None$

We know that $N^{+}(x_{0},A)$ contains a vertex $u$ such that
$d^{+}(u,N^{+}(x_{0},A)\leq 0.5(d^{+}(x_{0},A)-1)$. From this and (7) it
follows that $|N^{+2}(x_{0},A)|\geq n-k-0.5(d^{+}(x_{0},A)-1)$. It is not
difficult to see that
$N^{-}(x_{r},A)\rightarrow\\{x_{0},x_{1},\ldots,x_{r}\\}\cup
N^{+}(x_{0},A)\cup N^{+2}(x_{0},A)$. Therefore, $N^{-}(x_{r},A)$ contains a
vertex $y$ such that

$n=d^{+}(y)\geq|N^{+}(x_{0},A)|+|N^{+2}(x_{0},A)|+0.5(|N^{-}(x_{r},A)|-1)+r+1.$

Now, since $\min\\{|N^{+}(x_{0},A)|,|N^{-}(x_{r},A)|\\}\geq n-k-r$, we obtain
that $n=d^{+}(y)\geq 2n-2k+1$. Hence, $2k\geq n+1$, which contradicts that
$2k\leq n-2$. Claim 1 is proved.

Using Claim 1, $n\geq 5$ and $2k\leq n-2$, we obtain that $|A|\leq n$,
$r=2n-k-|A|\geq n-k\geq 3.5$ (i.e., $r\geq 4$) and

$\min\\{|N^{+}(x_{0},V(P))|,|N^{-}(x_{r},V(P))|\\}\geq n-k.$ $None$

Claim 2: $N^{+}(x_{1},A)=N^{-}(x_{r-1},A)=\emptyset$.

Proof: By the digraph duality, it suffices to prove that
$N^{-}(x_{r-1},A)=\emptyset$. Suppose, on the contrary, that
$N^{-}(x_{r-1},A)\not=\emptyset$. Let $z$ be a vertex in $N^{-}(x_{r-1},A)$.
Then $zx_{r-1}\in A(T)$, $z\rightarrow\\{x_{0},x_{1},\ldots,x_{r-1}\\}$ and
$|N^{-}(z,A)|\geq n-k-1$.

Case 2.1. $N^{-}(z,A)\rightarrow x_{r-1}$. Then

$A(\\{x_{0},x_{1},\ldots,x_{r-3}\\}\rightarrow\\{z\\}\cup N^{-}(z,A)\cup
N^{-2}(z,A))=\emptyset.$ $None$

Since $N^{-}(z,A)$ contains a vertex $u$ such that $d^{-}(u,N^{-}(z,A))\leq
0.5(|N^{-}(z,A)|-1)$, it follows that $|N^{-2}(z,A)|\geq
n-k-1-0.5(|N^{-}(z,A)|-1)$. Now using (9) and $r\geq n-k$, we obtain that
$\\{x_{0},x_{1},\ldots,x_{r-3}\\}$ contains a vertex $v$ such that

$n=d^{-}(v)\geq 0.5(r-3)+n-k-1-0.5(|N^{-}(z,A)|-1)+|N^{-}(z,A)|+1\geq
2n-2k-1.5,$

a contradiction to $2k\leq n-2$.

Case 2.2. $A(x_{r-1}\rightarrow N^{-}(z,A))\not=\emptyset$. Since $\\{z\\}\cup
N^{-}(z,A)\subseteq A$ and $|N^{-}(z,A)|\geq n-k-1$, we have that $|A|\geq
n-k$. Observe that

$N^{-}(z,A)\cup N^{-}(x_{r-1},A)\rightarrow\\{x_{0},x_{1},\ldots,x_{r-3}\\}.$
$None$

Hence, $\\{z\\}\cup N^{-}(z,A)\rightarrow x_{1}$, as $r\geq 4$. Therefore, for
some $y\in N^{-}(z,A)$, $x_{r-1}\rightarrow y\rightarrow x_{1}$. If
$x_{i}x_{r}\in A(T)$ with $i\in[1,r-2]$ (respectively, with $i\in[1,r-3]$),
then $x_{0}x_{i+1}\notin A(T)$ (respectively, $x_{0}x_{i+2}\notin A(T)$), for
otherwise $Q=x_{0}x_{i+1}\ldots x_{r-1}yx_{1}\ldots x_{i}x_{r}$ (respectively,
$Q=x_{0}x_{i+2}\ldots x_{r-1}yzx_{1}\ldots x_{i}x_{r}$), which is a
contradiction. From this and (8) we have,

$d^{-}(x_{0},\\{x_{2},x_{3},\ldots,x_{r-1}\\})\geq n-k-2.$ $None$

This together with $|A|\geq n-k$ and $A\rightarrow x_{0}$ implies that
$n=d^{-}(x_{0})\geq|A|+d^{-}(x_{0},\\{x_{2},\\\ x_{3},\ldots,x_{r-1}\\})\geq
2n-2k-2$, which in turn implies $2k=n-2$, $|A|=n-k$ (i.e., $A=\\{z\\}\cup
N^{-}(z,A)$), $r=n\geq 6$, $k\geq 2$ (as $n\geq 5$ and $n$ is even and
$r=2n-k-|A|$) and $d^{-}(x_{0},\\{x_{2},x_{3},\ldots,x_{r-1}\\})=n-k-2$. Now
by the above arguments, it is not difficult to see that
$N^{-}(x_{r},\\{x_{1},x_{2},\ldots,x_{r-2}\\})=\\{x_{k+1},x_{k+2},\ldots,x_{n-2}\\}$.
Since $yx_{2}\in A(T)$ (by (10) and $r\geq 6$), it follows that if
$x_{1}x_{i+1}\in A(T)$ with $i\in[k+1,n-2]$, then $Q=x_{0}x_{1}x_{i+1}\ldots
x_{n-1}yx_{2}\ldots x_{i}x_{n}$, a contradiction. We may therefore assume that
$d^{+}(x_{1},\\{x_{k+2},x_{k+3},\ldots,x_{n-1}\\})=0$. This together with
$d^{+}(x_{1},\\{x_{0}\\}\cup A)=0$ implies that $d^{-}(x_{1})\geq|A|+n-k-1\geq
2n-2k-1$, a contradiction. Claim 2 is proved.

From Claim 2 it follows that
$d^{-}(x_{r-1},\\{x_{0},x_{1},\ldots,x_{r-2}\\})\geq n-k$. Hence, $r\geq
n-k+1$. Using (11) and Claim 1, we obtain, $d^{-}(x_{0})\geq n-k-2+|A|$.
Therefore, $|A|\leq k+2$.

Claim 3: $|A|\leq k+1$.

Proof: The proof is by contradiction. Suppose that $|A|\geq k+2$. Then,
$|A|=k+2\geq 2$ and $r=2n-2k-2$ since $|A|\leq k+2$. This implies that $r$ is
even and $r\geq n\geq 6$ since $n\geq 5$ and $2k\leq n-2$. Since
$x_{r-1}\rightarrow A\rightarrow x_{1}$ (Claim 2), it is not difficult to see
that if $x_{i}x_{r}\in A(T)$ with $i\in[1,r-2]$, then $x_{0}x_{i+1}\notin
A(T)$ (for otherwise, $Q=x_{0}x_{i+1}\ldots x_{r-1}zx_{1}\ldots x_{i}x_{r}$,
where $z\in A$). This together with $A\rightarrow x_{0}$,
$d^{-}(x_{r},\\{x_{1},x_{2},\ldots,x_{r-2}\\})\geq n-k-2$ and $|A|=k+2$
implies that
$n=d^{-}(x_{0})\geq|A|+d^{-}(x_{r},\\{x_{1},x_{2},\ldots,x_{r-2}\\})\geq
k+2+n-k-2=n$. This means that
$d^{-}(x_{r},\\{x_{1},x_{2},\ldots,x_{r-2}\\}=n-k-2$ and the out-neighbors of
$x_{0}$ in $\\{x_{2},x_{3},\ldots,x_{r-1}\\}$ are only those vertices $x_{i}$
for which $x_{i-1}x_{r}\in A(T)$. From this we conclude that there is no
$i\in[1,r-3]$ such that $x_{i}x_{r}\in A(T)$ and $x_{i+1}x_{r}\notin A(T)$
since in the converse case $x_{0}x_{i+2}\in A(T)$ and $Q=x_{0}x_{i+2}\ldots
x_{r-1}a_{1}a_{2}zx_{1}\ldots x_{i}x_{r}$, where $a_{1},a_{2}\in A$ and
$a_{1}a_{2}\in A(T)$. Therefore,
$N^{-}(x_{r},\\{x_{1},x_{2},\ldots,x_{r-2}\\})=\\{x_{n-k-1},x_{n-k},\ldots,x_{r-2}\\}$
and
$N^{+}(x_{0},\\{x_{2},x_{3},\ldots,x_{r-1}\\})=\\{x_{2},x_{3},\ldots,x_{n-k-1}\\}$.
In particular, $x_{r}x_{1}\in A(T)$ as $n\geq 6$ and $n-k\geq 3$.

Assume first that for some $y\in A$, $yx_{2}\in A(T)$. Using the above
equalities, we obtain $\\{x_{n-k},x_{n-k+1},\ldots,x_{r-1}\\}\rightarrow
x_{1}$ (for otherwise, $Q=x_{0}x_{1}x_{j}\ldots x_{r-1}yx_{2}\ldots
x_{j-1}x_{r}$, where $j\in[n-k,r-1]$). Now, since
$A\cup\\{x_{0},x_{r}\\}\rightarrow x_{1}$ and $|A|=k+2$, we obtain
$d^{-}(x_{1})\geq n+2$, a contradiction.

Assume next that $A(A\rightarrow x_{2})=\emptyset$, i.e., $x_{2}\rightarrow
A$. Then $\\{x_{2},x_{3},\ldots,x_{r}\\}\rightarrow A$ and there is a vertex
$u\in A$ such that $d^{-}(u)\geq 2n-2k-3+(k+1)/2$. Therefore, $2k=n-2$ as
$2k\leq n-2$. Thus $k\leq 1$, which is a contradiction, since $2k=n-2$ and
$n\geq 6$. Claim 3 is proved.

Since $r=2n-k-|A|$, $|A|\leq k+1$ and $2k\leq n-2$, we have $r\geq n+1\geq 6$
as $n\geq 5$.

Claim 4: $N^{+}(x_{2},A)=N^{-}(x_{r-2},A)=\emptyset$.

Proof: By the digraph duality, it suffices to prove that
$N^{+}(x_{2},A)=\emptyset$. Suppose, on the contrary, that
$N^{+}(x_{2},A)\not=\emptyset$. Let $z$ be a vertex in $N^{+}(x_{2},A)$. Then
$\\{x_{2},x_{3},\ldots,x_{r}\\}\rightarrow z$. This together with
$z\rightarrow\\{x_{0},x_{1}\\}$ implies that $|N^{+}(z,A)|\geq n-k-2$ and
$|A|\geq n-k-1$. Now using the facts that $|A|\leq k+1$ (Claim 3) and $2k\leq
n-2$, we obtain that $2k=n-2$, $|A|=k+1$ and $r=n+1$. From $2k=n-2$ it follows
that $n$ is even, $n\geq 6$ (as $n\geq 5$) and $k\geq 2$. Since
$\\{x_{0}\\}\cup A\rightarrow x_{1}$ and $r=n+1$, it follows that there is a
vertex $x_{j}\in\\{x_{4},x_{5},\ldots,x_{n+1}\\}$ such that $x_{1}x_{j}\in
A(T)$. Therefore, if $x_{0}x_{2}\in A(T)$, then $Q=x_{0}x_{2}\ldots
x_{j-1}zx_{1}x_{j}\ldots x_{r}$, and if $x_{0}x_{3}\in A(T)$, then for some
$y\in N^{+}(z,A)$ we have $Q=x_{0}x_{3}\ldots x_{j-1}zyx_{1}x_{j}\ldots
x_{r}$, which is a contradiction. We may therefore assume that
$\\{x_{2},x_{3}\\}\rightarrow x_{0}$. Since $\\{x_{2},x_{3}\\}\cup
A\rightarrow x_{0}$, $\\{x_{2},x_{3},\ldots,x_{r}\\}\rightarrow z$ and
$r=n+1$, it follows that $d^{+}(x_{0},\\{x_{4},x_{5},\ldots,x_{n}\\})\geq
n-k-2\geq 2$ and $d^{+}(z,A)=k$. Let $x_{0}x_{m}\in A(T)$ with $m\in[4,n]$ and
$m$ is the minimum with these properties. Since $A\rightarrow x_{1}$,
$x_{n}z\in A(T)$ and $T\langle A\rangle$ contains a path $zyu$ of length two,
it is easy to see that $d^{-}(x_{n+1},\\{x_{m-3},x_{m-2},x_{m-1}\\})=0$ and if
$x_{0}x_{j}\in A(T)$ with $j\in[4,n]$, then $x_{j-1}x_{n+1}\notin A(T)$. These
together with $d^{-}(x_{n+1},A)=0$ and $|A|=k+1$ imply that
$d^{+}(x_{n+1})\geq|A|+n-k-2+2=n+1$, a contradiction. Claim 4 is proved.

From Claims 1, 2 and 4 it follows that $\\{x_{r},x_{r-1},x_{r-2}\\}\rightarrow
A\rightarrow\\{x_{0},x_{1},x_{2}\\}$.

Let $\alpha:=\max\\{i\in[2,r-3]\,|\,A\rightarrow x_{i}\\}$. From this and the
assumption that $T$ contains no $Q$ path it follows that
$A\rightarrow\\{x_{0},x_{1},\ldots,x_{\alpha}\\}$, $A(x_{j}\rightarrow
A)\not=\emptyset$ for all $j\in[\alpha+1,r]$ and $A$ contains a vertex $z$
such that

$\\{x_{\alpha+1},x_{\alpha+2},\ldots,x_{r}\\}\rightarrow
z\rightarrow\\{x_{0},x_{1},\ldots,x_{\alpha}\\}.$ $None$

Fact 1: (i) If $2k=n-2$, then $n$ is even (i.e., $n\geq 6$, as $n\geq 5$),
$n-k-|A|\geq 1$ and $r\geq n+1\geq 7$.

(ii) If $2k\leq n-3$, then $n-k-|A|\geq 2$ and $r\geq n+2\geq 7$.

Proof: Indeed, $n-k-|A|\geq n-2k-1$ and $r=2n-k-|A|\geq 2n-2k-1$ as $|A|\leq
k+1$. Now, if $2k=n-2$, then $n-k-|A|\geq 1$ and $r\geq n+1\geq 7$, and if
$2k\leq n-3$, then $n-k-|A|\geq 2$ and $r\geq n+2\geq 7$.

Fact 2: $n-k-|A|\leq\alpha\leq n-1-\lfloor\frac{1}{2}|A|\rfloor\leq n-1$.

Proof: Since $\\{x_{\alpha+1},x_{\alpha+2},\ldots,x_{r}\\}\rightarrow z$, we
have $n=d^{-}(z)\geq r-\alpha=2n-k-|A|-\alpha$ and $\alpha\geq n-k-|A|$. From
$A\rightarrow\\{x_{0},x_{1},\ldots,x_{\alpha}\\}$ it follows that there exists
a vertex $x\in A$ such that
$n=d^{+}(x)\geq\alpha+1+\lfloor\frac{1}{2}|A|\rfloor$. Hence, $\alpha\leq
n-1-\lfloor\frac{1}{2}|A|\rfloor\leq n-1$.

Let $B:=\\{x_{i}\mid
i\in[1,\alpha-1],\,\,A(x_{i}\rightarrow\\{x_{\alpha+2},\ldots,x_{r}\\})\not=\emptyset\\}$.

Proposition 1: (i) If $x_{i}\in B$, then
$A(\\{x_{0},x_{1},\ldots,x_{i-1}\\}\rightarrow x_{i+1})=\emptyset$.

(ii) If $x_{j}x_{r}\in A(T)$ with $j\in[\alpha,r-2]$, then
$A(\\{x_{0},x_{1},\ldots,x_{\alpha-1}\\}\rightarrow x_{j+1})=\emptyset$.

Proof: (i) $x_{i}\in B$ means that $i\in[1,\alpha-1]$ and there is an integer
$b\in[\alpha+2,r]$ such that $x_{i}x_{b}\in A(T)$. Assume that for some
$a\in[0,i-1]$, $x_{a}x_{i+1}\in A(T)$. By (12), $zx_{a+1},x_{b-1}z\in A(T)$.
Therefore, $Q=x_{0}\ldots x_{a}x_{i+1}\ldots x_{b-1}zx_{a+1}\ldots
x_{i}x_{b}\ldots x_{r}$, a contradiction. So,
$A(\\{x_{0},x_{1},\ldots,x_{i-1}\\}\rightarrow x_{i+1})=\emptyset$.

(ii) Now assume that $x_{j}x_{r}\in A(T)$ with $j\in[\alpha,r-2]$ and
$x_{i}x_{j+1}\in A(T)$ with $i\in[0,\alpha-1]$. Again using (12), we obtain
$Q=x_{0}x_{1}\ldots x_{i}x_{j+1}\ldots x_{r-1}zx_{i+1}\ldots x_{j}x_{r}$, a
contradiction.

Now, we divide the proof of Theorem 1.5 into two cases. Note that, by digraph
duality and Lemma 3.3, the second case easily follows from the first case.

Case I. $A(\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\}\rightarrow x_{r})=\emptyset$,
i.e., $x_{r}\rightarrow\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\}$.

For this case first we need to show the following claims below (Claims 5-13).

Claim 5: $B\not=\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\}$.

Proof: Suppose, on the contrary, that
$B=\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\}$. Let $\alpha\geq 3$. Then using
Proposition 1(i), we see that
$d^{+}(x_{1},\\{x_{0},x_{3},\ldots,x_{\alpha},x_{r}\\})=0$. From
$d^{-}(x_{r},V(P))\geq n-k$ and
$x_{r}\rightarrow\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\}$ it follows that
$d^{-}(x_{r},\\{x_{\alpha},x_{\alpha+1},\ldots,x_{r-2}\\})\geq n-k-2$.

By running $j$ from $\alpha$ to $r-2$ in Proposition 1(ii), we have

$d^{-}(x_{r},\\{x_{\alpha},x_{\alpha+1},\ldots,x_{r-2}\\})+d^{+}(x_{1},\\{x_{\alpha+1},x_{\alpha+2},\ldots,x_{r-1}\\})\leq
r-1-\alpha.$

Therefore,

$\displaystyle d^{-}(x_{1},\\{x_{\alpha+1},x_{\alpha+2},\ldots,x_{r-1}\\})$
$\displaystyle=$ $\displaystyle
r-1-\alpha-d^{-}(x_{1},\\{x_{\alpha+1},x_{\alpha+2},\ldots,x_{r-1}\\})$
$\displaystyle\geq$ $\displaystyle
d^{-}(x_{r},\\{x_{\alpha},x_{\alpha+1},\ldots,x_{r-2}\\})$ $\displaystyle\geq$
$\displaystyle n-k-2.$

Hence, by this inequality and $\alpha\geq n-k-|A|$ (Fact 2) we have

$n=d^{-}(x_{1})\geq|A|+|\\{x_{0},x_{3},\ldots,x_{\alpha},x_{r}\\}|+d^{-}(x_{1},\\{x_{\alpha+1},x_{\alpha+2},\ldots,x_{r-2}\\})$
$\geq|A|+\alpha+n-k-2\geq 2n-2k-2.$

Let now $\alpha=2$. From $2=\alpha\geq n-k-|A|$ it follows that $|A|\geq
n-k-2$. Therefore,

$n=d^{-}(x_{1})\geq|A|+|\\{x_{0},x_{r}\\}|+d^{-}(x_{1},\\{x_{\alpha+1},x_{\alpha+2},\ldots,x_{r-2}\\})$
$\geq|A|+2+n-k-2\geq 2n-2k-2.$

Since $k=|S|\leq(n-2)/2$, in both cases we have equalities, that is, $2k=n-2,$
$k\geq 2$, $\alpha=n-k-|A|$ and
$d^{-}(x_{r},\\{x_{\alpha},x_{\alpha+1},\ldots,x_{r-2}\\})=n-k-2$. From these
we obtain that
$|\\{x_{\alpha+1},x_{\alpha+2},\ldots,x_{r}\\}|=r-\alpha=2n-k-|A|-(n-k-|A|)=n$
and if $x_{l}x_{r}\notin A(T)$ with $l\in[\alpha,r-2]$, then $x_{1}x_{l+1}\in
A(T)$. Since $A(x_{\alpha}\rightarrow\\{x_{\alpha-1}\\}\cup A)=\emptyset$,
there exists $j\in[\alpha+2,r]$ such that $x_{\alpha}x_{j}\in A(T)$. If
$x_{\alpha}x_{r}\notin A(T)$, then $j\leq r-1$, $x_{1}x_{\alpha+1}\in A(T)$
(by the above observation) and $Q=x_{0}x_{1}x_{\alpha+1}\ldots
x_{j-1}zx_{2}\ldots x_{\alpha}x_{j}\ldots x_{r}$, a contradiction. We may
therefore assume that $x_{\alpha}x_{r}\in A(T)$. Since
$d^{-}(x_{r},\\{x_{\alpha},x_{\alpha+1},\ldots,x_{r-2}\\})$ $=n-k-2$ and
$|\\{x_{\alpha},x_{\alpha+1},\ldots,x_{r-4}\\}|=n-3\geq n-k-2$, it follows
that there is an integer $i\in[\alpha,r-4]$ such that $x_{i}x_{r}\in A(T)$ and
$x_{i+1}x_{r}\notin A(T)$. By our observation, $x_{1}x_{i+2}\in A(T)$.
Therefore, if $x_{i+1}x_{r-1}\in A(T)$, then $Q=x_{0}x_{1}x_{i+2}\ldots
x_{r-2}zx_{2}\ldots x_{i+1}x_{r-1}x_{r}$, and if $x_{r-1}x_{i+1}\in A(T)$,
then $Q=x_{0}x_{1}x_{i+2}\ldots x_{r-1}x_{i+1}zx_{2}\ldots x_{i}x_{r}$. In
both cases we have a contradiction. Claim 5 is proved.

From now on, by $T^{1}$ we denote the subtournament
$T\langle\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\}\rangle$.

Claim 6: $B\not=\emptyset$.

Proof: By contradiction, suppose that $B=\emptyset$. This means that
$A(\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\}$
$\rightarrow\\{x_{\alpha+2},x_{\alpha+3},\ldots,x_{r}\\})=\emptyset$, i.e.,
for any $i\in[1,\alpha-1]$,
$d^{-}(x_{i},\\{x_{\alpha+2},x_{\alpha+3},\ldots,x_{r}\\})=2n-k-|A|-\alpha-1$.

Case 6.1. The subtournament $T^{1}$ is not regular. Then by Lemma 3.1(iii),
there is a vertex $x\in V(T^{1})$ such that $d^{-}(x,V(T^{1}))\geq
0.5(\alpha-1)$. Therefore, since $r=2n-k-|A|$ and $\alpha\leq n-\lfloor
0.5|A|\rfloor-1$, we have

$n=d^{-}(x)\geq|A|+|\\{x_{\alpha+2},x_{\alpha+3},\ldots,x_{r}\\}|+0.5(\alpha-1)\geq
n+0.5(n-2k-2+\lfloor 0.5|A|\rfloor)$.

Since $2k\leq n-2$ and $|A|\geq 1$, we have that all inequalities in the last
inequality in fact are equalities, i.e., $|A|=1$, $2k=n-2$ ($n$ is even) and
$\alpha=n-0.5\lfloor|A|\rfloor-1=n-1$. If $x_{i}x_{r}\in A(T)$ with
$i\in[\alpha,r-2]$, then, since $\alpha=n-1$ and $|A|=1$, we have
$d^{+}(x_{i+1})\geq|A|+|\\{x_{0},x_{1},\ldots,x_{\alpha-1},x_{i+2}\\}|\geq
n+1$, a contradiction. We may therefore assume that
$x_{r}\rightarrow\\{x_{\alpha},x_{\alpha+1},\ldots,x_{r-2}\\}$. This together
with $x_{r}\rightarrow A\cup\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\}$ and
$2k=n-2$ implies that $d^{+}(x_{r})\geq 2n-k-2\geq n+1$, a contradiction.

Case 6.2. The subtournament $T^{1}$ is regular. Then
$d^{-}(x_{1},V(T^{1}))=0.5(\alpha-2)$. Since $B=\emptyset$, $2k\leq n-2$ and
$r=2n-k-|A|$, we have that
$n=d^{-}(x_{1})\geq|A|+|\\{x_{0},x_{\alpha+2},x_{\alpha+3},\ldots,x_{r}\\}|+0.5(\alpha-2)\geq
n+0.5(n-\alpha)$, a contradiction since $\alpha\leq n-1$. Claim 6 is proved.

By Claim 4, $\alpha\geq 2$. If $\alpha=2$, then $B=\emptyset$ or
$B=\\{x_{1}\\}=\\{x_{1},\ldots,x_{\alpha-1}\\}$, violating Claim 5 or Claim 6.
Therefore, $\alpha\geq 3$ and $A\rightarrow\\{x_{0},x_{1},x_{2},x_{3}\\}$. By
the digraph duality, $\\{x_{r-3},x_{r-2},x_{r-1},x_{r}\\}\rightarrow A$.

Claim 7: $|B|\geq 2n-2k-\alpha-3$.

Proof: By Claim 5, $\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\}\setminus
B\not=\emptyset$.

Assume first that the subtournament
$T^{2}:=T\langle\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\}\setminus B\rangle$ is
not regular. By Lemma 3.1(iii), $V(T^{2})$ contains a vertex $x$ such that
$d^{-}(x,V(T^{2}))\geq 0.5|V(T^{2})|$. On the other hand, from the definition
of $B$ it follows that
$A\cup\\{x_{\alpha+2},x_{\alpha+3},\ldots,x_{r}\\}\rightarrow x$. Therefore,

$n=d^{-}(x)\geq|A|+r-\alpha-1+0.5(\alpha-1-|B|)=n+0.5(2n-2k-\alpha-3-|B|).$

Hence, $|B|\geq 2n-2k-\alpha-3$.

Assume next that $T^{2}$ is regular. Then for all $x_{i}\in V(T^{2})$,
$d^{-}(x_{i},V(T^{2}))=0.5(\alpha-|B|-2)$. Let $x_{q}\in V(T^{2})$ and $q$ is
the minimum with this property. Then

$n=d^{-}(x_{q})\geq|A\cup\\{x_{q-1},x_{\alpha+2},x_{\alpha+3},\ldots,x_{r}\\}|+0.5(\alpha-|B|-2)$
$=n+0.5(2n-2k-\alpha-2-|B|).$

Hence, $|B|\geq 2n-2k-\alpha-2$. Claim 7 is proved.

Let
$M:=\\{x_{j}\,|\,j\in[\alpha+2,r-1]\,\hbox{and}\,A(\\{x_{0},x_{1},\ldots,x_{\alpha-1}\\}\rightarrow
x_{j})\not=\emptyset\\}$.

Proposition 2: If $x_{j}\in M$, then $x_{j-1}x_{r}\notin A(T)$.

Proof: If $x_{j}\in M$ and $x_{j-1}x_{r}\in A(T)$, by the definition of $M$
there is a vertex $x_{i}$ with $i\in[0,\alpha-1]$ such that $x_{i}x_{j}\in
A(T)$. Therefore, $Q=x_{0}x_{1}\ldots x_{i}x_{j}\ldots x_{r-1}zx_{i+1}\ldots
x_{j-1}x_{r}$, a contradiction.

Claim 8: $M\not=\\{x_{\alpha+2},x_{\alpha+3},\ldots,x_{r-1}\\}$.

Proof: Suppose, on the contrary, that
$M=\\{x_{\alpha+2},x_{\alpha+3},\ldots,x_{r-1}\\}$. From $d^{-}(x_{r},$
$\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\})=0$ (by the condition of Case I) and
Proposition 2 it follows that

$n=d^{+}(x_{r})\geq|A|+|\\{x_{1},x_{2},\ldots,x_{\alpha-1},x_{\alpha+1},x_{\alpha+2},\ldots,x_{r-2}\\}|=2n-k-3.$

Hence, $n-k\leq 3$. Since $2k\leq n-2$, we obtain that $n\leq 4$, which
contradicts that $n\geq 5$. Claim 8 is proved.

From Claim 8 it follows that
$\\{x_{\alpha+2},x_{\alpha+3},\ldots,x_{r-1}\\}\setminus M\not=\emptyset$.

Claim 9: $2|M|\geq 2n-2k-\alpha-3$.

Proof: Assume first that the subtournament $T^{1}$ is not regular. Then
$V(T^{1})$ contains a vertex $x$ such that $d^{-}(x,V(T^{1}))\geq
0.5(\alpha-1)$. This together with
$A\cup(\\{x_{\alpha+2},x_{\alpha+3},\ldots,x_{r}\\}\setminus M)\rightarrow x$
and $r=2n-k-|A|$ implies that

$n=d^{-}(x)\geq|A|+0.5(\alpha-1)+r-\alpha-1-|M|=n+0.5(2n-2k-2|M|-\alpha-3).$

Hence, $2|M|\geq 2n-2k-\alpha-3$. Assume next that $T^{1}$ is regular. Then,
$d^{-}(x_{1},V(T^{1}))=0.5(\alpha-2)$. Now by a similar argument as above, we
obtain

$n=d^{-}(x_{1})\geq|A|+|\\{x_{0}\\}|+0.5(\alpha-2)+r-\alpha-1-|M|=n+0.5(2n-2k-2|M|-\alpha-2).$

Hence, $2|M|\geq 2n-2k-\alpha-2$. Claim 9 is proved.

From Claim 9, $2k\leq n-2$ and $\alpha\leq n-\lfloor 0.5|A|\rfloor-1$ it
follows that $2|M|\geq 2n-2k-\alpha-3\geq\lfloor 0.5|A|\rfloor$. Hence, if
$|M|=0$ (i.e., $M=\emptyset$), then $2k=n-2$, $|A|=1$ and $\alpha=n-\lfloor
0.5|A|\rfloor-1=n-1$. In particular, $|M|=0$ means that
$x_{r-1}\rightarrow\\{x_{0},x_{1},\ldots,x_{\alpha-1}\\}$. This together with
$x_{r-1}\rightarrow\\{x_{r}\\}\cup A$ implies that $d^{+}(x_{r-1})\geq n+1$,
which is a contradiction. Therefore, $M\not=\emptyset$.

Let $W:=\\{x_{i}\,\,\hbox{with}\,\,i\in[\alpha+1,r-1]\,|\,\hbox{there
exists}\,\,j\in[\alpha,i-1]\,\,\hbox{such that}\,x_{j}x_{r}\in A(T)$
$\hbox{and}\,\,|\\{x_{j+1},\ldots,x_{i}\\}|\leq\lfloor
0.5|\\{x_{j+1},\ldots,x_{r}\\}|\rfloor\\}$.

By Lemma 3.4, $A(\\{x_{0},x_{1},\ldots,x_{\alpha-1}\\}\rightarrow
W)=\emptyset$, i.e., $W\rightarrow\\{x_{0},x_{1},\ldots,x_{\alpha-1}\\}$.

Let $x_{\alpha+s}x_{r}\in A(T)$, $s\geq 0$ and $s$ is the minimum with this
property.

Claim 10: $|W|\geq n-k-2+\lfloor 0.5(n-|A|-\alpha-s+1)\rfloor$.

Proof: Under the condition of Case I, we have that
$x_{r}\rightarrow\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\}$ and
$d^{-}(x_{r},\\{x_{\alpha+s},x_{\alpha+s+1},\ldots,x_{r-2}\\})\geq n-k-2\geq
2$. Without loss of generality, we may assume that
$\\{x_{\alpha+s+1},x_{\alpha+s+2},\ldots,x_{\alpha+s+m},x_{\alpha+s+m+1},\ldots,x_{\alpha+s+m+t}\\}\subseteq
W$, where $m\geq 0$, $x_{\alpha+s+m}x_{r}\in A(T)$,
$x_{\alpha+s+m+1}x_{r}\notin A(T)$, $x_{\alpha+s+m+t+1}\notin W$ and
$t=\lfloor(r-m-\alpha-s)/2\rfloor$. Let
$Y:=\\{x_{i+1}\,|\,i\in[\alpha+s+m+t+1,r-2],\,x_{i}x_{r}\in A(T)\\}$. It is
not difficult to see that $Y\subseteq W$, $m\geq n-k-3-|Y|$ and
$|W|\geq|Y|+m+t$. Since $r=2n-k-|A|$, it is not hard to check that

$|W|\geq\lfloor\frac{2|Y|+m+r-\alpha-s}{2}\rfloor\geq
n-k-2+\lfloor\frac{n-|A|+|Y|-\alpha-s+1}{2}\rfloor.$

Therefore, Claim 10 is true, since $|Y|\geq 0$.

We know that

$\\{x_{r}\\}\cup A\cup W\rightarrow\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\}.$
$None$

Claim 11: $x_{\alpha}x_{r}\notin A(T)$, i.e., $s\geq 1$.

Proof: By contradiction, suppose that $x_{\alpha}x_{r}\in A(T)$, i.e.,
$\alpha=0$.

Case 11.1. The subtournament $T^{1}$ is regular. Using Claim 10 (when $s=0$)
and $2k\leq n-2$, we obtain $d^{-}(x_{1})\geq|\\{x_{0},x_{r}\\}\cup A\cup
W|+0.5(\alpha-2)\geq 0.5(3n-2k-2+|A|)>n$, which is a contradiction.

Case 11.2. The subtournament $T^{1}$ is not regular. If
$d^{-}(x_{j},V(T^{1}))\geq\alpha/2$ for some $x_{j}\in V(T^{1})$, then using
(13), Claim 10 and $2k\leq n-2$, we obtain

$d(x_{j})\geq|\\{x_{r}\\}\cup A\cup
W|+\alpha/2\geq|A|+1+\alpha/2+n-k-2+0.5(n-|A|-\alpha)$ $=0.5(3n-2k+|A|-2)>n,$

a contradiction. We may therefore assume that for all $x_{i}\in V(T^{1})$,
$d^{-}(x_{i},V(T^{1}))<\alpha/2$. Therefore by Lemma 3.1(v), $T^{1}$ is almost
regular. Then for all $x_{i}\in V(T^{1})$,
$d^{-}(x_{i},V(T^{1}))\geq(\alpha-3)/2$. Again using (13), we obtain

$n=d^{-}(x_{1})\geq|\\{x_{0},x_{r}\\}\cup A\cup W|+0.5(\alpha-3)\geq
n+0.5(n-2k-3+|A|).$

Hence, $2k=n-2$, $|A|=1$ ($A=\\{z\\}$), $d^{-}(x_{1},V(T^{1}))=(\alpha-3)/2$,
$N^{-}(x_{1})=\\{x_{0},x_{r}\\}\cup A\cup W\cup N^{-}(x_{1},V(T^{1}))$. Since
$\alpha\geq 3$ and $x_{\alpha}\notin W$, we have that $x_{1}x_{\alpha}\in
A(T)$. If $x_{\alpha-1}x_{j}\in A(T)$ with $j\in[\alpha+2,r]$, then
$Q=x_{0}x_{1}x_{\alpha}\ldots x_{j-1}zx_{2}\ldots x_{\alpha-1}x_{j}\ldots
x_{r}$, if $x_{\alpha-1}x_{\alpha+1}\in A(T)$, then $Q=x_{0}x_{1}\ldots
x_{\alpha-1}x_{\alpha+1}\ldots x_{r-1}zx_{\alpha}x_{r}$. Thus, in both cases
we have a contradiction. Therefore,
$\\{x_{\alpha+1},x_{\alpha+2},\ldots,x_{r}\\}\rightarrow x_{\alpha-1}$. Now,
since $|A|=1$ and $2k=n-2$, we have

$n=d^{-}(x_{\alpha-1})\geq|\\{z\\}|+|\\{x_{\alpha+1},x_{\alpha+2},\ldots,x_{r}\\}|+d^{-}(x_{\alpha-1},V(T^{1}))\geq
n+(n-\alpha-1)/2.$

Therefore, $\alpha=n-1$ since $\alpha\leq n-1$. Then,
$x_{\alpha+1}\rightarrow\\{z,x_{\alpha+2},x_{0},x_{1},\ldots,x_{\alpha-1}\\}$
by Proposition 1(ii). This means that $d^{+}(x_{\alpha+1})\geq n+1$, a
contradiction. Claim 11 is proved.

Let
$F:=\\{x_{i}\,|\,i\in[\alpha+1,\alpha+s]\,\,\hbox{and}\,\,d^{-}(x_{i},\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\})\geq
1\\}$.

Then, $\\{x_{\alpha+1},\ldots,x_{\alpha+s}\\}\setminus
F\rightarrow\\{x_{1},\ldots,x_{\alpha-1}\\}$.

Claim 12: $|F|\geq\lfloor 0.5(s+1)\rfloor$.

Proof: Recall that $x_{\alpha+s}x_{r}\in A(T)$, $s\geq 1$ and
$x_{r}\rightarrow\\{x_{1},\ldots,x_{\alpha-1}\\}$. Suppose, on the contrary,
that $|F|<\lfloor 0.5(s+1)\rfloor$. Then
$|\\{x_{\alpha+1},\ldots,x_{\alpha+s}\\}\setminus F|\geq\frac{1}{2}(s+1)$ (for
this it suffices to consider when $s$ is even or not). Therefore, for every
vertex $x_{i}\in\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\}$,
$d^{-}(x_{i},\\{x_{\alpha+1},\ldots,x_{\alpha+s}\\})\geq\frac{1}{2}(s+1)$.
Assume first that the subtournament $T^{1}$ is not regular. Then $V(T^{1})$
contains a vertex $x$ such that $d^{-}(x,V(T^{1}))\geq 0.5(\alpha-1)$. Now
using Claim 10, $2k\leq n-2$ and the fact that $\\{x_{r}\\}\cup A\cup
W\rightarrow x$, we obtain

$d^{-}(x)\geq|A\cup\\{x_{r}\\}\cup W|+0.5(\alpha-1)+0.5(s+1)\geq n+0.5|A|,$

a contradiction. Assume next that the subtournament $T^{1}$ is regular. Then
$d^{-}(x_{1},V(T^{1}))\\\ =0.5(\alpha-2)$. Therefore, as the above, we obtain

$d^{-}(x)\geq|A\cup\\{x_{0},x_{r}\\}\cup W|+0.5(\alpha-2)+0.5(s+1)\geq
n+0.5(|A|+1),$

a contradiction. Claim 12 is proved.

Claim 13: $A(A\rightarrow x_{\alpha+s+1})\not=\emptyset$.

Proof: Suppose, on the contrary, that $A(A\rightarrow
x_{\alpha+s+1})=\emptyset$. Then $\\{x_{\alpha+s+1},\ldots,x_{r}\\}\rightarrow
A$. Since $W\subseteq\\{x_{\alpha+s+1},\ldots,x_{r-1}\\}$ it follows that
$W\rightarrow A$. Recall that $x_{\alpha+s}x_{r}\in A(T)$, $s\geq 1$ and
$\alpha+s$ is the minimum with this property. By Proposition 1(i), we know
that if $x_{i}\in B$ with $i\geq 2$, then $x_{i+1}x_{1}\in A(T)$ and
$x_{i+1}\notin W$. By the definition of $F$,
$\\{x_{\alpha+1},\ldots,x_{\alpha+s}\\}\setminus F\rightarrow x_{1}$. Now
using Claims 7 and 10, we obtain

$n=d^{-}(x_{1})\geq|A|+|B|-1+|W|+|\\{x_{0},x_{r}\\}|+|\\{x_{\alpha+1},\ldots,x_{\alpha+s}\\}\setminus
F|$ $\geq|A|+2n-2k-\alpha-4+n-k-2+0.5(n-|A|-\alpha-s)+2+s-|F|$
$=n+0.5(|A|+s-2|F|+5n-6k-3\alpha-8).$

Therefore, $0\geq|A|+s-2|F|+5n-6k-3\alpha-8$.

Now we consider the set $W$. We know that
$W\rightarrow\\{x_{0},x_{1},\ldots,x_{\alpha-1}\\}$ (by Lemma 3.4). Note that
if $x_{i}\in W$, then $i\geq\alpha+s+1$ and $x_{i-1}z\in A(T)$. Using this, it
is not difficult to show that if $x_{j}\in F$ and $x_{i}\in W$, then
$x_{i}x_{j-1}\in A(T)$. Thus we have, if $x_{j}\in F$, then $W\rightarrow
x_{j-1}$. If $T\langle W\rangle$ is not regular, then for some $x\in W$,
$d^{+}(x,W)\geq 0.5|W|$, if $T\langle W\rangle$ is regular, then for $x_{l}\in
W$ with the maximum index we have, $d^{+}(x_{l},W\cup\\{x_{l+1}\\})\geq
0.5(|W|+1)$. In both cases, for some $x_{j}\in W$,
$d^{+}(x_{j},W\cup\\{x_{l+1}\\})\geq 0.5|W|$. Therefore there is a vertex
$x_{j}\in W$ such that

$n=d^{+}(x_{j})\geq|A|+|F|+0.5|W|+|\\{x_{0},x_{1},\ldots,x_{\alpha-1}\\}|$
$\geq|A|+|F|+\alpha+0.5(n-k-2+0.5(n-|A|-\alpha-s))$
$=(3|A|+3\alpha+4|F|+3n-2k-4-s)/4.$

Therefore, $0\geq 3|A|+3\alpha+4|F|-n-2k-4-s$. Together with
$0\geq|A|+s-2|F|+5n-6k-3\alpha-8$ and $n\geq 2k+2$, we obtain $0\geq
2|A|+|F|-2,$ which is a contradiction since $|A|\geq 1,|F|\geq 1$, and thus
$2|A|+|F|-2\geq 1.$ Claim 13 is proved.

Now we are ready to complete the discussion of Case I. Let
$q:=max\\{i\,|\,A(A\rightarrow x_{i})\not=\emptyset\\}$. Let now $zx_{q}\in
A(A\rightarrow x_{q})$. Then $z\rightarrow\\{x_{0},x_{1},\ldots,x_{q}\\}$ and
$q\leq n-1$. Note that $3\leq\alpha\leq q\leq r-4$ and
$\\{x_{q+1},x_{q+2},\ldots,x_{r}\\}\rightarrow A$. In this case (Case I) we
have $A(\\{x_{1},x_{2},\ldots,x_{\alpha}\\}\rightarrow x_{r})=\emptyset$ as
$s\geq 1$. From $A(A\rightarrow x_{\alpha+s+1})\not=\emptyset$ it follows that
$q\geq\alpha+s+1$. Observe that $|A|\geq 2$ since $\alpha+s>\alpha$,
$A(A\rightarrow x_{\alpha+s})\not=\emptyset$ and $A(x_{\alpha+s}\rightarrow
A)\not=\emptyset$. From $q\geq\alpha+s+1\geq\alpha+2$ and
$x_{\alpha+s}x_{r}\in A(T)$ it follows that there is an integer
$p\in[\alpha+s,q-1]$ such that $x_{p}x_{r}\in A(T)$. Let $p$ be the maximum
with this property. Now using the first part of Lemma 3.3, we obtain
$A(\\{x_{0},x_{1},\ldots,x_{p-2}\\}\rightarrow\\{x_{q+2},x_{q+3},\ldots,x_{r-1}\\})=\emptyset,$
which in turn implies that (since $p-2\geq\alpha-1$)

$A(\\{x_{0},x_{1},\ldots,x_{\alpha-1}\\}\rightarrow\\{x_{q+2},x_{q+3},\ldots,x_{r-1}\\})=\emptyset.$
$None$

Let $m:=max\\{i\in[1,r-2]\,|\,x_{i}x_{r}\in A(T)\\}$ and consider two cases
depending on $m$.

Case I.1. $m\not=p$. Then $m\geq q$ (since $p<q$). Using the facts that
$\\{x_{q+1},x_{q+2},\ldots,x_{r}\\}\\\ \rightarrow A$ and
$z\rightarrow\\{x_{0},x_{1},\ldots,x_{q}\\}$, we obtain
$x_{m+1}\rightarrow\\{x_{0},x_{1},\ldots,x_{q-1}\\}$ (for otherwise,
$x_{j}x_{m+1}\in A(T)$ with $j\in[0,q-1]$ and $Q=x_{0}x_{1}\ldots
x_{j}x_{m+1}\ldots x_{r-1}zx_{j+1}\ldots x_{m}x_{r}$, a contradiction).
Therefore,

$n=d^{+}(x_{m+1})\geq|A|+|\\{x_{0},x_{1},\ldots,x_{q-1},x_{m+2}\\}|=|A|+q+1.$

Hence, $q\leq n-|A|-1$, which in turn implies that
$|\\{x_{q+2},x_{q+3},\ldots,x_{r-1}\\}|=r-q-2\geq n-k-1.$ By the definition of
the set $M$ and (14), we have that
$M\subseteq\\{x_{\alpha+2},x_{\alpha+3},\ldots,x_{q+1}\\}$. Let $x_{j+1}\in
M$. Then $\alpha+1\leq j\leq q$, and by Proposition 2, for all $i\in[q+2,r]$,
$x_{j}x_{i}\notin A(T)$ (for otherwise, if $x_{j}x_{i}\in A(T)$ for some
$i\in[q+2,r]$, then by the definition of $M$ there is a vertex $x_{g}$ with
$g\in[0,\alpha-1]$ such that $x_{g}x_{j+1}\in A(T)$, and hence
$Q=x_{0}x_{1}\ldots x_{g}x_{j+1}\ldots x_{i-1}zx_{g+1}\ldots x_{j}x_{i}\ldots
x_{r}$, a contradiction). Therefore, $\\{x_{q+2},x_{q+3},\ldots,\\\
x_{r-1}\\}$ contains a vertex $x$ such that
$n=d^{+}(x)\geq|A|+|\\{x_{0},x_{1},\ldots,x_{\alpha-1}\\}|+|M|+0.5(r-q-3)$.
Now using Claim 9 and the facts that $r-q-2\geq n-k-1$ and $\alpha\geq
n-k-|A|$, we obtain

$n=d^{+}(x)\geq|A|+\alpha+0.5(2n-2k-\alpha-3)+0.5(n-k-2)$ $\geq
n+0.5(|A|+2n-4k-5)\geq n+0.5(|A|-1),$

which is a contradiction since $|A|\geq 2$.

Case I.2. $m=p<q$. Recall that $s\geq 1$ and
$d^{-}(x_{r},\\{x_{\alpha+s},x_{\alpha+s+1},\ldots,x_{m-2}\\})\geq n-k-4\geq
0$. By the first part of Lemma 3.3 (when in Lemma 3.3, $s=m$ and $t=r$) we
have

$A(\\{x_{0},x_{1},\ldots,x_{m-2}\\}\rightarrow\\{x_{q+2},x_{q+3},\ldots,x_{r-1}\\})=\emptyset.$
$None$

It is easy to see that $|\\{x_{0},x_{1},\ldots,x_{m-2}\\}|\geq n-k+\alpha-3$
since $d^{-}(x_{r},\\{x_{1},x_{2},\ldots,x_{\alpha}\\})=0$. We have that
$|\\{x_{q+1},\ldots,x_{r-1}\\}|\geq 2n-k-|A|-q-1\geq n-k-|A|$ as $q\leq n-1$.
Since $\alpha+s+1\leq m\leq q-1$ and $|A|\geq 2$, it follows that for some
$y\in A\setminus\\{z\\}$, $x_{\alpha+s}y\in A(T)$. If $q=n-1$, then $yz\in
A(T)$. Therefore, $Q=x_{0}x_{1}\ldots x_{\alpha+s}yzx_{\alpha+s+2}\ldots
x_{r}$, a contradiction. From now on, assume that $q\leq n-2$. Then
$|\\{x_{q+2},\ldots,x_{r-1}\\}|\geq n-k-|A|$.

Assume first that the subtournament
$T^{3}:=T\langle\\{x_{q+2},\ldots,x_{r-1}\\}\rangle$ is regular. Then,
$d^{+}(x_{r-1},V(T^{3}))\geq 0.5(n-k-|A|-1)$. This together with $m\geq
n-k+\alpha-2$, (15) and $\alpha\geq n-k-|A|$ implies that

$n=d^{+}(x_{r-1})\geq|A|+|\\{x_{0},x_{1},\ldots,x_{m-2},x_{r}\\}|+0.5(n-k-|A|-1)$
$=|A|+m+0.5(n-k-|A|-1)\geq|A|+n-k+\alpha-2+0.5(n-k-|A|-1)$
$\geq|A|+n-k-2+n-k-|A|+0.5(n-k-|A|-1)$ $=2n-2k-2+0.5(n-k-|A|-1).$

If $|A|\leq k$ or $2k\leq n-3$, then the last inequality gives a
contradiction. We may therefore assume that $2k=n-2$ and $|A|=k+1$. Then from
$\alpha\geq 3$ and $\alpha\geq n-k-|A|$ it follows that $\alpha\geq
n-k-|A|+2$. Now it is not difficult to check that $d^{+}(x_{r-1})\geq
n-k+\alpha-2+|A|+0.5(n-k-|A|-1)\geq n+2$, which is a contradiction.

Assume next that the subtournament $T^{3}$ is not regular. Then $V(T^{3})$
contains a vertex $x$ such that $d^{+}(x,V(T^{3}))\geq 0.5(n-k-|A|)$. Hence by
(15),

$d^{+}(x)\geq n-k+\alpha-3+|A|+0.5(n-k-|A|).$ $None$

If $2k\leq 2n-3$, then using the last inequality, $|A|\leq k+1$ and
$\alpha\geq n-k-|A|$, we obtain that $d^{+}(x)\geq n+1$, which is a
contradiction. We may therefore assume that $2k=n-2$. Observe that when
$2k=n-2$, then from $\alpha\geq 3$ and $\alpha\geq n-k-|A|$ it follows that if
$|A|=k$, then $\alpha\geq n-k-|A|+1$, and if $|A|=k+1$, then $\alpha\geq
n-k-|A|+2$. If $|A|\leq k-1$, then using (16), $2k=n-2$ and $\alpha\geq
n-k-|A|$, we obtain $d^{+}(x)>n$, a contradiction. We may therefore assume
that $k\leq|A|\leq k+1$. Then by the above observation, $\alpha\geq
n-k-|A|+1$, which together with (16) implies that $d^{+}(x)>n$, which is a
contradiction. The discussion of Case I.2 is completed.

Case II. $A(\\{x_{1},x_{2},\ldots,x_{\alpha-1}\\}\rightarrow
x_{r})\not=\emptyset$. Let $x_{p}x_{r}\in A(T)$ with $p\in[1,\alpha-1]$. If
$A(x_{0}\rightarrow\\{x_{\alpha+2},x_{\alpha+3},\ldots,x_{r-1}\\})=\emptyset$,
then by considering the converse tournament of $T$ we reduce the case to Case
I since for some $\beta\in[\alpha+1,r-3]$,
$\\{x_{\beta+1},x_{\beta+2},\ldots,x_{r}\\}\rightarrow A$. By the digraph
duality, we may assume that
$A(x_{0}\rightarrow\\{x_{\alpha+2},x_{\alpha+3},\ldots,x_{r-1}\\})\not=\emptyset$.
Let $x_{0}x_{i}\in A(T)$ with $i\in[\alpha+2,r-1]$. From (12) and the first
part of Lemma 3.3 (when in Lemma 3.3, $s=p$ and $t=r$) it follows that $p=1$.
Since $r\geq 7$ (Fact 1), we have that $t-s\geq 6$. Thus, $x_{1}x_{r}\in A(T)$
and $x_{0}x_{i}\in A(T)$ with $i\in[\alpha+2,r-1]$, which contradicts the
second part of Lemma 3.3. This contradiction completes the proof of Theorem
1.5. ∎

Remark 4: The following example of a tournament of order $2n+1=9$ shows that
Theorem 1.5 for $n=4$ is not true. Consider a tournament $H$ such that
$V(H)=\\{x,y,u,v,z\\}\cup A\cup B$, where $A=\\{a_{1},a_{2}\\}$ and
$B=\\{b_{1},b_{2}\\}$, with the properties $x\rightarrow\\{u,v,z\\}\rightarrow
y$, $B\rightarrow\\{u,v\\}\rightarrow A$, $y\rightarrow A\cup B\rightarrow x$,
$A\rightarrow z\rightarrow B$ and the following
$xy,uv,vz,zu,a_{1}a_{2},b_{1}b_{2},a_{1}b_{1}$,
$a_{2}b_{2},b_{2}a_{1},a_{2}b_{1}$ arcs are in $A(H)$.

It is easy to see that $H-\\{z\\}$ contains an $(x,y)$-path of length 3, but
contains no $(x,y)$-path of length 4.

Acknowlegement We are very grateful to the referees for their careful reading
of the manuscript and a large number of useful suggestions.

## References

  * [1] B. Alspach, “Cyles of each length in regular tournaments”, Canadian Mathematical Bulleten, Vol. 10, no. 2, pp. 283-286, 1967.
  * [2] B. Alspach, K.B. Reid and D.P. Roselle, “Bypasses in Asymmetric Digraphs,” Journal of Combinatorial Theory, Vol. 17, no.1, pp. 11-18, 1974.
  * [3] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer-Verlag, London, 2000.
  * [4] J. Bang-Jensen and F. Havet, Tournaments and semicomplete digraphs, in Classes of Directed Graphs (J. Bang-Jensen and G. Gutin, eds) , Springer-Verlag, London, 2018.
  * [5] J. Bang-Jensen and G. Gutin, “Paths, Trees and Cycles in tournaments”, Congressus Numerantium, vol. 115, pp. 131-170, 1996.
  * [6] J.-C. Bermond and C. Thomassen, “Cycles in Digraphs-A survey”, Journal of Graph Theory, vol. 5, pp. 1-43, 1981.
  * [7] M. Darah, Y.-P. Liu, C.-Q. Zang, Cycles of all lengths in arc-3-cyclic semi-complete digraphs. Discrete Mathematics, 173(1-3) 23-33, 1997.
  * [8] S. Kh. Darbinyan, “Bypasses in tournaments”, Akad. Nauk Armyan. SSR Dokl., vol. 66, no. 3, pp. 138-141, 1978.
  * [9] S. Kh. Darbinyan, “Bypasses in regular tournaments”, Thesises of reports All-union conference of the problem theoretical cybernetics, pp. 133-134, Novosibirsk, 1977.
  * [10] S. Kh. Darbinyan , “On panconnected tournaments”, Preprint of Computer Center of Akad. Nauk Armyan. SSR, p. 15, 1979.
  * [11] F. Havet, “Pancyclic arcs and connectivity in tournaments”, Journal of Graph Theory, vol.47, no. 2, pp. 87-110, 2004.
  * [12] O.S. Jacobsen, “Cyles and paths in tournaments”, PhD Thesis, University of Aarhus, 1972.
  * [13] X. Lu, “A note on Min-Max pair in Tournaments” Graphs and Combinatorics, vol. 35, pp. 1139-1145, 2019.
  * [14] J. Moon, Some mapping problems for theory tournaments”, Graph Theory and its Applications (B,Harris, editor), Academic Press, New York, pp. 133-148, 1970.
  * [15] T. Yao, Y. Guo and K. Zhang, “Pancyclic out-arcs of a vertex in tournaments”, Discrete Applied Mathematics, vol. 99, 245-249, 2000.
  * [16] A. Yeo, “The number of pancyclic arcs in a $k$-strong tournament”, Journal of Graph Theory, vol.50, pp. 212-219, 2005.
  * [17] C. Thomassen “Hamiltonian-Connected Tournaments”, Journal of Combinatorial Theory Ser. B, vol. 28, pp. 142-163, 1980.
  * [18] K.-M. Zhang, “Completely Path-Connected Tournaments”, Journal of Combinatorial Theory Ser. B, vol. 33, pp. 166-177, 1982.


# A Hodge theoretic extension of Shapley axioms

Tongseok Lim  Tongseok Lim: Krannert School of Management
Purdue University, West Lafayette, Indiana 47907, USA<EMAIL_ADDRESS>
###### Abstract.

Lloyd S. Shapley [19, 20] introduced a set of axioms in 1953, now called the
Shapley axioms, and showed that the axioms characterize a natural allocation
among the players who are in grand coalition of a cooperative game. Recently,
Stern and Tettenhorst [23] showed that a cooperative game can be decomposed
into a sum of component games, one for each player, whose value at the grand
coalition coincides with the Shapley value. The component games are defined by
the solutions to the naturally defined system of least squares linear
equations via the framework of the Hodge decomposition on the hypercube graph.

In this paper we propose a new set of axioms which characterizes the component
games. Furthermore, we realize them through an intriguing stochastic path
integral driven by a canonical Markov chain. The integrals are natural
representation for the expected total contribution made by the players for
each coalition, and hence can be viewed as their fair share. This allows us to
interpret the component game values for each coalition also as a valid measure
of fair allocation among the players in the coalition. Our axioms may be
viewed as a completion of Shapley axioms in view of this characterization of
the Hodge-theoretic component games, and moreover, the stochastic path
integral representation of the component games may be viewed as an extension
of the Shapley formula.

©2021 by the author.

_Keywords: Shapley axioms, Shapley value, Shapley formula, cooperative game,
component game, Hodge decomposition, least squares, path integral
representation_

_MSC2020 Classification: 91A12, 05C57, 68R01_

##  1\. Introduction

Let ${\mathbb{N}}$ denote the set of positive integers. For
$N\in{\mathbb{N}}$, let $[N]:=\\{1,2,...,N\\}$ denote the set of players. The
set of _cooperative games_ is defined by

${\cal G}_{N}=\\{v:2^{[N]}\to{\mathbb{R}}\ |\ v(\emptyset)=0\\}.$

Thus a cooperative game here is simply a (value) function on the subsets of
$[N]$, where each $S\subseteq[N]$ represents a coalition of players in $S$,
and $v(S)$ represents the value assigned to the coalition $S$, where the null
coalition $\emptyset$ receives zero value.

Lloyd Shapley considered the question of how to split the grand coalition
value $v([N])$ among the players for a given game $v\in{\cal G}_{N}$. It is
uniquely defined according to the following theorem, which is quoted from
Stern and Tettenhorst [23].

######  Theorem 1.1 (Shapley [20]).

There exists a unique allocation $v\in{\cal
G}_{N}\mapsto\bigl{(}\phi_{i}(v)\bigr{)}_{i\in[N]}$ satisfying the following
conditions:

$\cdot$ efficiency: $\sum_{i\in[N]}\phi_{i}(v)=v([N])$.

$\cdot$ symmetry:
$v\bigl{(}S\cup\\{i\\}\bigr{)}=v\bigl{(}S\cup\\{j\\}\bigr{)}$ for all
$S\subseteq[N]\setminus\\{i,j\\}$ yields $\phi_{i}(v)=\phi_{j}(v)$.

$\cdot$ null-player: $v\bigl{(}S\cup\\{i\\}\bigr{)}-v(S)=0$ for all
$S\subseteq[N]\setminus\\{i\\}$ yields $\phi_{i}(v)=0$.

$\cdot$ linearity: $\phi_{i}(\alpha
v+\alpha^{\prime}v^{\prime})=\alpha\phi_{i}(v)+\alpha^{\prime}\phi_{i}(v^{\prime})$
for all $\alpha,\alpha^{\prime}\in\mathbb{R}$ and $v,v^{\prime}\in{\cal
G}_{N}$.

Moreover, this allocation is given by the following explicit formula:

(1.1) $\phi_{i}(v)=\sum_{S\subseteq[N]\setminus\\{i\\}}\frac{\lvert
S\rvert!\bigl{(}N-1-\lvert
S\rvert\bigr{)}!}{N!}\Bigl{(}v\bigl{(}S\cup\\{i\\}\bigr{)}-v(S)\Bigr{)}.$

The four conditions listed above are often called the _Shapley axioms_. Quoted
from [23], they say that [efficiency] the value obtained by the grand
coalition is fully distributed among the players, [symmetry] equivalent
players receive equal amounts, [null-player] a player who contributes no
marginal value to any coalition receives nothing, and [linearity] the
allocation is linear in the game values.

(1.1) can be rewritten also quoted from [23]: Suppose the players form the
grand coalition by joining, one-at-a-time, in the order defined by a
permutation $\sigma$ of $[N]$. That is, player $i$ joins immediately after the
coalition $S_{\sigma,i}=\bigl{\\{}j\in[N]:\sigma(j)<\sigma(i)\bigr{\\}}$ has
formed, contributing marginal value
$v\bigl{(}S_{\sigma,i}\cup\\{i\\}\bigr{)}-v(S_{\sigma,i})$. Then $\phi_{i}(v)$
is the average marginal value contributed by player $i$ over all $N!$
permutations $\sigma$, i.e.,

(1.2)
$\phi_{i}(v)=\frac{1}{N!}\sum_{\sigma}\Bigl{(}v\bigl{(}S_{\sigma,i}\cup\\{i\\}\bigr{)}-v(S_{\sigma,i})\Bigr{)}.$

We see an important principle here, which we may call the Shapley’s principle:

Shapley’s principle. The value allocated to player $i$ is based entirely on
the marginal values $v\bigl{(}S\cup\\{i\\}\bigr{)}-v(S)$ the player $i$
contribute.

Extensive research on the cooperative and noncooperative games have been
inspired by and evolved from the pioneering study by Shapley [19, 20, 21, 22],
and various concepts of solutions have been proposed, e.g., Kalai and Samet
[8], Ruiz et al. [18] and Kultti and Salonen [12]. In particular, the
combinatorial Hodge decomposition has recently been applied to game theory in
various contexts, including noncooperative games (Candogan et al. [1]),
cooperative games (Stern and Tettenhorst [23]), and also other interesting
problems in economics, e.g., ranking of social preferences (Jiang et al. [7]).
In addition, there have been efforts to model various cooperation
restrictions, e.g., Faigle and Kern [5], Khmelnitskaya et al. [9], and
Koshevoy et al. [11]. On the other hand, computational aspects of Shapley
theory have been studied by Castro et al. [3, 2] and Deng and Papadimitriou
[4]. We refer to Lim [13] for an elementary introduction to the Hodge theory
on graphs, while more general and profound theory of Hodge goes back to Hodge
[6] and Kodaira [10]. For more comprehensive treatment of game theory, we
refer to e.g. Roth [16, 17], Peters [15].

In particular, Stern and Tettenhorst [23] showed that, given a game $v\in{\cal
G}_{N}$, there exist component games $v_{i}\in{\cal G}_{N}$ for each player
$i\in[N]$ which are naturally defined via the combinatorial Hodge
decomposition, satisfying $v=\sum_{i\in[N]}v_{i}$. Moreover, it holds
$v_{i}([N])=\phi_{i}(v)$, hence they obtained a new characterization of the
Shapley value as the value of the grand coalition in each player’s component
game.

In this context, the combinatorial Hodge decomposition boils down to the
Fundamental Theorem of Linear Algebra. For finite-dimensional inner product
spaces $X,Y$ and a linear map $\mathrm{d}:X\to Y$ and its adjoint
$\mathrm{d}^{*}:Y\to X$ given by $\langle\mathrm{d}x,y\rangle_{Y}=\langle
x,\mathrm{d}^{*}y\rangle_{X}$, FTLA asserts that the orthogonal decompositions
hold:

$X=\mathcal{R}(\mathrm{d}^{\ast})\oplus\mathcal{N}(\mathrm{d}),\qquad
Y=\mathcal{R}(\mathrm{d})\oplus\mathcal{N}(\mathrm{d}^{\ast}),$

where $\cal R(\cdot)$, ${\cal N}(\cdot)$ stand for the range and nullspace
respectively.

In order to introduce the work of [23], let us briefly review the setup. Let
$G=(V,E)$ be an oriented graph, where $V$ is the set of vertices and
$E\subseteq V\times V$ is the set of edges. “Oriented” means at most one of
$(a,b)$ and $(b,a)$ is in $E$ for $a,b\in V$. If $f\colon
E\rightarrow\mathbb{R}$ and $(a,b)\in E$, define $f(b,a)\coloneqq-f(a,b)$ for
the reverse-oriented edge. Let $\ell^{2}(V)$ be the space of functions
$V\rightarrow\mathbb{R}$ with the inner product

$\langle u,v\rangle\coloneqq\sum_{a\in V}u(a)v(a).$

Similarly, denote by $\ell^{2}(E)$ the space of functions
$E\rightarrow\mathbb{R}$ with inner product

$\langle f,g\rangle\coloneqq\sum_{(a,b)\in E}f(a,b)g(a,b).$

Next, define a linear operator
$\mathrm{d}\colon\ell^{2}(V)\rightarrow\ell^{2}(E)$, the gradient, by

$\mathrm{d}u(a,b)\coloneqq u(b)-u(a).$

Then its adjoint $\mathrm{d}^{\ast}\colon\ell^{2}(E)\rightarrow\ell^{2}(V)$,
the (negative) divergence, is given by

$(\mathrm{d}^{\ast}f)(a)=\sum_{b\sim a}f(b,a),$

where $b\sim a$ denotes that $(a,b)\in E$ or $(b,a)\in E$.

Now to study the cooperative games, given the set of players $[N]$, Stern and
Tettenhorst [23] applied the above setup to the _hypercube graph_ $G=(V,E)$,
where

$V=2^{[N]},\qquad E=\bigl{\\{}\bigl{(}S,S\cup\\{i\\}\bigr{)}\in V\times V\ |\
S\subseteq[N]\setminus\\{i\\},\ i\in[N]\bigr{\\}}.$

Notice each vertex $S\subseteq[N]$ can correspond to a vertex of the unit
hypercube in ${\mathbb{R}}^{N}$, and each edge is oriented in the direction of
the inclusion $S\hookrightarrow S\cup\\{i\\}$.

For each $i\in[N]$, let
$\mathrm{d}_{i}\colon\ell^{2}(V)\rightarrow\ell^{2}(E)$ denote the partial
differential operator

$\mathrm{d}_{i}u\bigl{(}S,S\cup\\{j\\}\bigr{)}=\begin{cases}\mathrm{d}u\bigl{(}S,S\cup\\{i\\}\bigr{)}&\text{if
}\ j=i,\\\ 0&\text{if }\ j\neq i.\end{cases}$

Thus $\mathrm{d}_{i}v\in\ell^{2}(E)$ encodes the marginal value contributed by
player $i$ to the game $v$, which is a natural object to consider in view of
the Shapley’s principle. Indeed, given $v\in{\cal G}_{N}$, Stern and
Tettenhorst [23] defined the component game $v_{i}$ for each $i\in[N]$ as the
unique solution in ${\cal G}_{N}$ to the following least squares
equation111The equation $\mathrm{d}u=f$ is solvable if only if
$f\in\mathcal{R}(\mathrm{d})$. When $f\notin\mathcal{R}(\mathrm{d})$, a least
squares solution to $\mathrm{d}u=f$ instead solves $\mathrm{d}u=f_{1}$ where
$f=f_{1}+f_{2}$ with $f_{1}\in\mathcal{R}(\mathrm{d})$,
$f_{2}\in\mathcal{N}(\mathrm{d}^{\ast})$ given by FTLA. By applying
$\mathrm{d}^{\ast}$, we get
$\mathrm{d}^{\ast}\mathrm{d}u=\mathrm{d}^{\ast}f_{1}=\mathrm{d}^{\ast}f$. The
substitution $u\to v_{i}$ and $f\to\mathrm{d}_{i}v$ yields (1.3).

(1.3) $\mathrm{d}^{\ast}\mathrm{d}v_{i}=\mathrm{d}^{\ast}\mathrm{d}_{i}v$

and showed that the component games satisfy some natural properties analogous
to the Shapley axioms (see [23, Theorem 3.4]). Moreover, by applying the
(pseudo) inverse of the Laplacian $\mathrm{d}^{\ast}\mathrm{d}$ to (1.3), they
provided an explicit formula for $v_{i}$ (see [23, Theorem 3.11]). In
particular, for the pure bargaining game $\delta_{[N]}$, defined by

$\delta_{[N]}([N])=1,\quad\delta_{[N]}(S)=0\,\text{ if }\,S\subsetneq[N]$

they also showed the complex general formulas in [23, Theorem 3.11] could be
simplified (see [23, Theorem 3.13]) due to the substantial symmetry of this
game.

Let us, for example, calculate the $v_{i}$’s for the pure bargaining game
$\delta_{[N]}$ when $N=2,3$ using the formulas in [23, Theorem 3.13]. For
$N=2$, one can compute

$\displaystyle v_{1}(\\{1\\})=v_{2}(\\{2\\})=\frac{1}{4},\
v_{1}(\\{2\\})=v_{2}(\\{1\\})=-\frac{1}{4},\
v_{1}(\\{1,2\\})=v_{2}(\\{1,2\\})=\frac{1}{2},$

and $v_{i}(\emptyset)=0$. For $N=3$, one can compute

$\displaystyle v_{1}(\\{1\\})=v_{2}(\\{2\\})=v_{3}(\\{3\\})=\frac{1}{12},$
$\displaystyle
v_{1}(\\{2\\})=v_{1}(\\{3\\})=v_{2}(\\{1\\})=v_{2}(\\{3\\})=v_{3}(\\{1\\})=v_{3}(\\{2\\})=-\frac{1}{24},$
$\displaystyle
v_{1}(\\{2,3\\})=v_{2}(\\{1,3\\})=v_{3}(\\{1,2\\})=-\frac{1}{4},$
$\displaystyle
v_{1}(\\{1,2\\})=v_{1}(\\{1,3\\})=v_{2}(\\{1,2\\})=v_{2}(\\{2,3\\})=v_{3}(\\{1,3\\})=v_{3}(\\{2,3\\})=\frac{1}{8},$
$\displaystyle
v_{1}(\\{1,2,3\\})=v_{2}(\\{1,2,3\\})=v_{3}(\\{1,2,3\\})=\frac{1}{3}.$

While we would not try to further compute for $N\geq 4$, we already see, for
example, $v_{i}$ can take negative values even when $v$ is nonnegative, as
already noted in [23].

This leads us to ask the following question: What is the economic meaning of
the $v_{i}(S)$ (except for $v_{i}([N])$, as it coincides with the Shapley
value $\phi_{i}(v)$)?

In this paper we assert that, just as $v_{i}([N])$, $v_{i}(S)$ can also
represent a fair allocation to the player $i$ of the value $v(S)$ for each
coalition $S$. We shall justify this in two different angles. First, we
present a set of new axioms which completely characterizes the component
games. Our axioms will be an extension of the Shapley axioms, and may be seen
as a completion in view of this characterization of the Hodge-theoretic
component games. In particular, the Discussion (iv) in Section 2 explains why
the new reflection axiom can be regarded natural in view of the Shapley
principle, and therefore, why the component value $v_{i}(S)$ can be
interpreted as a fair allocation. Second, we present the value function
$V_{i}(S)$ described by a stochastic path integral which is a natural
representation of the total contribution by the player $i$, on average, toward
each coalition $S$. Hence the value $V_{i}(S)$ can also be regarded as a fair
allocation of $v(S)$ to the player $i$. Now Theorem 3.1 verifies a remarkable
connection between stochastic path integrals and Hodge theory. From the
coincidence $V_{i}=v_{i}$, we further justify our assertion, namely,
$v_{i}(S)=V_{i}(S)$ can be viewed a fair allocation for the player $i$ and for
each terminal coalition state $S$.

##  2\. An extension of Shapley axioms

Let ${\cal G}=\bigcup_{N\in{\mathbb{N}}}{\cal G}_{N}$. For $i,j\in[N]$ and
$S\subseteq[N]$, define $S^{ij}\subseteq[N]$ by

$S^{ij}=\begin{cases}S&\text{if }\ S\subseteq[N]\setminus\\{i,j\\}\,\text{ or
}\,\\{i,j\\}\subseteq S,\\\ S\cup\\{i\\}\setminus\\{j\\}&\text{if }\ i\notin
S\,\text{ and }\,j\in S,\\\ S\cup\\{j\\}\setminus\\{i\\}&\text{if }\ j\notin
S\,\text{ and }\,i\in S.\end{cases}$

Given $v\in{\cal G}_{N}$, define $v^{ij}\in{\cal G}_{N}$ by
$v^{ij}(S)=v(S^{ij})$. Intuitively, the contributions of the players $i,j$ in
the game $v$ are interchanged in the game $v^{ij}$.

Of course, a cooperative game can be considered on any finite set of players
$M$ through a bijection $M\hookrightarrow[|M|]$. In this sense, for $v\in{\cal
G}_{N}$ and $i\in[N]$, we define $v_{-i}$ to be the restricted game of $v$ on
the set of players $[N]\setminus\\{i\\}$, i.e. $v_{-i}(S)=v(S)$ for all
$S\subseteq[N]\setminus\\{i\\}$. We are ready to describe our extension of
Shapley axioms.

######  Theorem 2.1.

There exists a unique allocation $v\in{\cal
G}\mapsto\bigl{(}\Phi_{i}[v]\bigr{)}_{i\in{\mathbb{N}}}$ satisfying
$\Phi_{i}[v]\in{\cal G}_{N}$ with $\Phi_{i}[v]\equiv 0$ if $i\geq N+1$ for
$v\in{\cal G}_{N}$, and moreover the following:

A1(efficiency): $v=\sum_{i\in{\mathbb{N}}}\Phi_{i}[v]$.

A2(symmetry): $\Phi_{i}[v^{ij}](S^{ij})=\Phi_{j}[v](S)$ for all $v\in{\cal
G}_{N}$, $i,j\in[N]$ and $S\subseteq[N]$.

A3(null-player): If $v\in{\cal G}_{N}$ and $\mathrm{d}_{i}v=0$ for some
$i\in[N]$, then $\Phi_{i}[v]\equiv 0$, and

$\Phi_{j}[v](S\cup\\{i\\})=\Phi_{j}[v](S)=\Phi_{j}[v_{-i}](S)\ \text{ for all
}\ j\in[N]\setminus\\{i\\},\,S\subseteq[N]\setminus\\{i\\}.$

A4(linearity): For any $v,v^{\prime}\in{\cal G}_{N}$ and
$\alpha,\alpha^{\prime}\in{\mathbb{R}}$, $\Phi_{i}[\alpha
v+\alpha^{\prime}v^{\prime}]=\alpha\Phi_{i}[v]+\alpha^{\prime}\Phi_{i}[v^{\prime}]$.

A5(reflection): For any $v\in{\cal G}_{N}$, $i\in[N]$ and
$S,T\subseteq[N]\setminus\\{i\\}$, it holds

$\Phi_{i}[v](S\cup\\{i\\})-\Phi_{i}[v](T\cup\\{i\\})=-\bigl{(}\Phi_{i}[v](S)-\Phi_{i}[v](T)\bigr{)}.$

Moreover, the solutions $(v_{i})_{i\in[N]}$ to (1.3) satisfy A1–A5 with
$\Phi_{i}[v]=v_{i}$.

Discussion. (i) A1, A4 seem natural analogues of corresponding Shapley axioms.

(ii) The condition in A2 is just as if the players $i,j$ exchange their
labels. We may interpret as, if the contributions of $i,j$ are interchanged,
then so are their payoffs.

(iii) A3 says that if $\mathrm{d}_{i}v=0$ then everything is just as if $i$ is
not present. In other words, if player $i$ contributes nothing, then the
reward of the rest is independent of the participation of the null player $i$,
and hence by efficiency, the player $i$ receives nothing. So
$\Phi_{i}[v]\equiv 0$ is in fact a consequence rather than a part of the
axioms.

(iv) Perhaps A5 – which is newly introduced – is the least intuitive of all
the axioms. To convince its innocuousness, let
$S,T\subseteq[N]\setminus\\{i\\}$, and consider an arbitrary connected path
$\theta$ of cooperation process from $S$ to $T$ on the hypercube graph:

$\theta:X_{0}\to X_{1}\to\dots\to X_{n}$

where $X_{0}=S$, $X_{n}=T$, and each $(X_{k},X_{k+1})$ is either a forward- or
reverse-oriented edge of the hypercube graph. Then there exists its reflection
with respect to $i$:

$\theta^{\prime}:X^{\prime}_{0}\to X^{\prime}_{1}\to\dots\to X^{\prime}_{n}$

where $X^{\prime}_{k}:=X_{k}\cup\\{i\\}$ if $i\notin X_{k}$, and
$X^{\prime}_{k}:=X_{k}\setminus\\{i\\}$ if $i\in X_{k}$. Now observe that the
contribution of the player $i$ (i.e. the integral of $\mathrm{d}_{i}$) along
the path $\theta$ and $\theta^{\prime}$ have the opposite sign, since whenever
the player $i$ joins / leaves coalition along $\theta$, $i$ leaves / joins
coalition along $\theta^{\prime}$ respectively. In view of the Shapley’s
principle and the arbitrariness of $\theta$, this is the rationale for us to
adopt the reflection axiom. Note that while (1.2) takes into account the
coalition processes of joining direction only, our consideration above allows
for the coalitions to proceed in either direction.

Now we present a proof of Theorem 2.1.

###### Proof.

We claim that A1–A5 determines the linear operator $\Phi$ uniquely (if
exists). For each $N\in{\mathbb{N}}$, define the basis games $\delta_{S,N}$ of
${\cal G}_{N}$ for every $S\subseteq[N]$, $S\neq\emptyset$, by

$\delta_{S,N}(S)=1,\quad\delta_{S,N}(T)=0\,\text{ if }\,T\neq S.$

We proceed by an induction on $N$. The case $N=1$ is already from A1. Suppose
the claim holds for $N-1$, so $\Phi_{i}[\delta_{S,N-1}]$ are determined for
all $S\in 2^{[N-1]}\setminus\\{\emptyset\\}$. Now define the games
$\Delta_{(S,S\cup\\{i\\})}$ in ${\cal G}_{N}$ for each $i\in[N]$,
$S\subseteq[N]\setminus\\{i\\}$, $S\neq\emptyset$, by

$\Delta_{(S,S\cup\\{i\\})}(T)=1\,\text{ if }\,T=S\text{ or
}T=S\cup\\{i\\},\quad\Delta_{(S,S\cup\\{i\\})}(T)=0\,\text{ otherwise.}$

Notice then A3 determines $\Phi$ for all $\Delta_{(S,S\cup\\{i\\})}\in{\cal
G}_{N}$. By A4, to prove the claim, it is enough to show A1–A5 can determine
$\Phi$ for the pure bargaining game $\delta:=\delta_{[N],N}$.

By A2, $\sum_{S\subseteq[N]}\Phi_{i}[\delta](S)$ is constant for all
$i\in[N]$, thus it is $1/N$ by A1. Define

$u_{i}(S):=\Phi_{i}[\delta](S)-\frac{1}{N2^{N}}\ \text{ for all }\
S\subseteq[N]$

so that $u_{i}(\emptyset)=-\frac{1}{N2^{N}}$ and
$\sum_{S\subseteq[N]}u_{i}(S)=0$ for all $i$. Now observe A5 implies:

$u_{i}(S)+u_{i}(S\cup\\{i\\})\text{ is constant for all
}S\subseteq[N]\setminus\\{i\\},\text{ hence it is zero.}$

This determines $u_{i}$ thus $\Phi_{i}[\delta]$ as follows: suppose $u_{i}(S)$
has been determined for all $i$ and $|S|\leq k-1$. Let $|T|=k$. Then we have
$u_{i}(T)=-u_{i}(T\setminus\\{i\\})$ for all $i\in T$ and it is constant (say
$c_{k}$) by A2. Then by A1 and A2, $u_{j}(T)=-\frac{kc_{k}}{N-k}$ for all
$j\notin T$. By induction, the proof of uniqueness of the operator $\Phi$ is
therefore complete.

It remains to show the solutions $(v_{i})_{i\in[N]}$ to (1.3) satisfy A1–A5
with $\Phi_{i}[v]=v_{i}$. Note that $v_{i}\in{\cal G}_{N}$ is uniquely
determined by (1.3) since $\cal N(\mathrm{d})$ is one-dimensional space
spanned by the constant game ${\mathds{1}}_{N}\equiv 1\in\ell^{2}(2^{[N]})$,
and since $v_{i}(\emptyset)=0$.

A4 is clearly satisfied by $(v_{i})_{i}$. To show A1, we compute similarly as
in [23]:

$\mathrm{d}^{\ast}\mathrm{d}\sum_{i\in[N]}v_{i}=\sum_{i\in[N]}\mathrm{d}^{\ast}\mathrm{d}v_{i}=\sum_{i\in[N]}\mathrm{d}^{\ast}\mathrm{d}_{i}v=\mathrm{d}^{\ast}\sum_{i\in[N]}\mathrm{d}_{i}v=\mathrm{d}^{\ast}\mathrm{d}v,$

since $\mathrm{d}=\sum_{i\in[N]}\mathrm{d}_{i}$. Hence by unique solvability
of (1.3), $\sum_{i\in[N]}v_{i}=v$ as desired.

Next let $\sigma$ be a permutation of $[N]$. As in [23], let $\sigma$ act on
$\ell^{2}(V)$ and $\ell^{2}(E)$ via

$\sigma v(S)=v(\sigma(S))\,\text{ and }\,\sigma
f\bigl{(}S,S\cup\\{i\\}\bigr{)}=f\bigl{(}\sigma(S),\sigma(S\cup\\{i\\})\bigr{)},\
\ v\in\ell^{2}(V),\ f\in\ell^{2}(E).$

It is easy to check $\mathrm{d}\sigma=\sigma\mathrm{d}$ and
$\mathrm{d}_{i}\sigma=\sigma\mathrm{d}_{\sigma(i)}$. We also have
$\mathrm{d}^{\ast}\sigma=\sigma\mathrm{d}^{\ast}$, since

$\langle v,\mathrm{d}^{\ast}\sigma f\rangle=\langle\mathrm{d}v,\sigma
f\rangle=\langle\sigma^{-1}\mathrm{d}v,f\rangle=\langle\mathrm{d}\sigma^{-1}v,f\rangle=\langle\sigma^{-1}v,\mathrm{d}^{\ast}f\rangle=\langle
v,\sigma\mathrm{d}^{\ast}f\rangle$

for any $v\in\ell^{2}(V)$ and $f\in\ell^{2}(E)$. Now let $\sigma$ be the
transposition of $i,j$. We have

$\mathrm{d}^{\ast}\mathrm{d}(\sigma
v)_{i}=\mathrm{d}^{\ast}\mathrm{d}_{i}\sigma
v=\mathrm{d}^{\ast}\sigma\mathrm{d}_{j}v=\sigma\mathrm{d}^{\ast}\mathrm{d}_{j}v=\sigma\mathrm{d}^{\ast}\mathrm{d}v_{j}=\mathrm{d}^{\ast}\mathrm{d}\sigma
v_{j}$

which shows $(\sigma v)_{i}=\sigma v_{j}$ by the unique solvability. Notice
this corresponds to A2.

For A3, let $v\in{\cal G}_{N}$, $i\in[N]$, and let $\mathrm{d}_{i}v=0$. Then
by (1.3) we readily get $v_{i}\equiv 0$. Fix $j\neq i$, and let
$\mathrm{\tilde{d}}$, $\mathrm{\tilde{d}}_{j}$ be the differential operators
restricted on $[N]\setminus\\{i\\}$, and let $\tilde{v}=v_{-i}$, i.e.,
$\tilde{v}$ is the restricted game of $v$ on $[N]\setminus\\{i\\}$. Let
$\tilde{v}_{j}$ be the corresponding component game on $[N]\setminus\\{i\\}$,
solving the defining equation
$\mathrm{\tilde{d}}^{\ast}\mathrm{\tilde{d}}\tilde{v}_{j}=\mathrm{\tilde{d}}^{\ast}\mathrm{\tilde{d}}_{j}\tilde{v}$.
Finally, in view of A3, define $v_{j}\in{\cal G}_{N}$ by $v_{j}=\tilde{v}_{j}$
on $2^{[N]\setminus\\{i\\}}$ and $\mathrm{d}_{i}v_{j}=0$. Now observe that A3
will follow if we verify this $v_{j}$ indeed solves the equation
$\mathrm{d}^{\ast}\mathrm{d}v_{j}=\mathrm{d}^{\ast}\mathrm{d}_{j}v$.

To show this, let $S\subseteq[N]\setminus\\{i\\}$. In fact the following
string of equalities holds:

$\mathrm{d}^{\ast}\mathrm{d}v_{j}(S\cup\\{i\\})=\mathrm{d}^{\ast}\mathrm{d}v_{j}(S)=\mathrm{\tilde{d}}^{\ast}\mathrm{\tilde{d}}\tilde{v}_{j}(S)=\mathrm{\tilde{d}}^{\ast}\mathrm{\tilde{d}}_{j}\tilde{v}(S)=\mathrm{d}^{\ast}\mathrm{d}_{j}v(S)=\mathrm{d}^{\ast}\mathrm{d}_{j}v(S\cup\\{i\\})$

which simply follows from the definition of the differential operators. For
instance

$\displaystyle\mathrm{d}^{\ast}\mathrm{d}v_{j}(S)=\sum_{T\sim
S}\mathrm{d}v_{j}(T,S)=\sum_{T\sim S,\,T\neq
S\cup\\{i\\}}\mathrm{d}v_{j}(T,S)=\mathrm{\tilde{d}}^{\ast}\mathrm{\tilde{d}}\tilde{v}_{j}(S)$

where the second equality is due to $\mathrm{d}_{i}v_{j}=0$. On the other
hand, since $j\neq i$,

$\displaystyle\mathrm{d}^{\ast}\mathrm{d}_{j}v(S)=\sum_{T\sim
S}\mathrm{d}_{j}v(T,S)=\sum_{T\sim
S}\mathrm{d}_{j}\tilde{v}(T,S)=\mathrm{\tilde{d}}^{\ast}\mathrm{\tilde{d}}_{j}\tilde{v}(S).$

The first and last equalities in the string should now be obvious, verifying
A3.

Finally we verify A5. For this, we need to verify the following claim

$v_{i}(S)+v_{i}(S\cup\\{i\\})\,\text{ is constant over all
}\,S\subseteq[N]\setminus\\{i\\}.$

Let $S\subseteq[N]\setminus\\{i\\}$, and recall
$\mathrm{d}^{\ast}\mathrm{d}_{i}v(S)=v(S)-v(S\cup\\{i\\})=-\mathrm{d}^{\ast}\mathrm{d}_{i}v(S\cup\\{i\\})$.
Hence
$\mathrm{d}^{\ast}\mathrm{d}v_{i}(S)+\mathrm{d}^{\ast}\mathrm{d}v_{i}(S\cup\\{i\\})=0$.
Define $w_{i}\in\ell^{2}(2^{[N]})$ by $w_{i}(S)=v_{i}(S\cup\\{i\\})$ and
$w_{i}(S\cup\\{i\\})=v_{i}(S)$. Then it is clear
$\mathrm{d}^{\ast}\mathrm{d}v_{i}(S\cup\\{i\\})=\mathrm{d}^{\ast}\mathrm{d}w_{i}(S)$,
thus $\mathrm{d}^{\ast}\mathrm{d}(v_{i}+w_{i})\equiv 0$, hence
$v_{i}+w_{i}\in\mathcal{N}(\mathrm{d})$, meaning $v_{i}+w_{i}$ is constant.
This proves the claim. ∎

##  3\. A path integral representation of the component games

Recall the Shapley value $\phi_{i}(v)=v_{i}([N])$ admits the representation
formula (1.2). For $v\in{\cal G}_{N}$, could $v_{i}(S)$ for $S\subsetneq[N]$
also have an analogous representation?

To give an answer, consider a Markov chain
$(X_{n})_{n\in{\mathbb{N}}\cup\\{0\\}}$ on the state space $2^{[N]}$,
$X_{0}=\emptyset$, equipped with the transition probability $p_{S,T}$ from $S$
to $T$ as follows:

$p_{S,T}=1/N\,\text{ if }(S,T)\text{ is a forward- or reverse-oriented edge,
}\ p_{S,T}=0\text{ otherwise.}$

Let $(\Omega,{\cal F},{\cal P})$ be the underlying probability space for
formality. For each $S\subseteq[N]$, let $\tau_{S}=\tau_{S}(\omega)$ denote
the first time the Markov chain $\big{(}X_{n}(\omega)\big{)}_{n}$ visits $S$.
We define the total contribution of the player $i$ along the sample path
$\omega\in\Omega$ toward $S$ by

${\mathrm{D}}_{i}v(S)={\mathrm{D}}_{i}v(S)(\omega):=\sum_{n=1}^{\tau_{S}(\omega)}\mathrm{d}_{i}v\big{(}X_{n-1}(\omega),X_{n}(\omega)\big{)}.$

Finally, we define value functions for each $i\in[N]$ via the following path
integral

$V_{i}(S)=V_{i}[v](S):=\int_{\Omega}{\mathrm{D}}_{i}v(S)(\omega)d{\cal
P}(\omega)={\mathbb{E}}[{\mathrm{D}}_{i}v(S)].$

Observe that $V_{i}(S)$ represents the expected total contribution made by
player $i$ toward the cooperation $S$, and hence can be interpreted as a fair
allocation of the value $v(S)$ to the player $i$ given the coalition process
would terminate at $S$.

Now the following theorem shows $V_{i}$ is a valid representation of the
component game $v_{i}$. This gives a further justification for the
interpretation of the component game value $v_{i}(S)$ to be a fair and natural
reward allocation for the player $i$ at $S$.

######  Theorem 3.1.

For every $v\in{\cal G}_{N}$ and $i\in[N]$ it holds $V_{i}=v_{i}$, where
$v_{i}\in{\cal G}_{N}$ is the unique solution to the equation (1.3)
characterized by A1–A5 in Theorem 2.1.

###### Proof.

Fix $v\in{\cal G}_{N}$. We may show that $(V_{i})_{i\in[N]}$ satisfies A1–A5
with $\Phi_{i}(v):=V_{i}$ thanks to Theorem 2.1. A4 may be trivially verified
and we omit. For A1, notice

$\sum_{i\in[N]}{\mathrm{D}}_{i}v(S)=\sum_{i\in[N]}\sum_{n=1}^{\tau_{S}}\mathrm{d}_{i}v\big{(}X_{n-1},X_{n}\big{)}=\sum_{n=1}^{\tau_{S}}\mathrm{d}v\big{(}X_{n-1},X_{n}\big{)}=v(S)$

since $\mathrm{d}=\sum_{i}\mathrm{d}_{i}$. Hence
$\sum_{i}V_{i}(S)={\mathbb{E}}[\sum_{i}{\mathrm{D}}_{i}v(S)]=v(S)$. This
verifies A1.

For $i\neq j$, note that each sample path $\omega$ has its counterpart
$\omega^{ij}$ satisfying

$X_{n}(\omega)=S\ \text{ if and only if }\ X_{n}(\omega^{ij})=S^{ij}\ \text{
for every $n\in{\mathbb{N}}$ and }S\subseteq[N]$

and moreover,
${\mathrm{D}}_{i}v(S)(\omega)={\mathrm{D}}_{j}v(S^{ij})(\omega^{ij})$. Taking
expectation then verifies A2.

For A3, assume $\mathrm{d}_{i}v=0$. Then ${\mathrm{D}}_{i}v=0$ readily gives
$V_{i}\equiv 0$. Next we may proceed by an induction on $N$, so let
$(\tilde{X}_{n})_{n}$ denote the Markov chain on the state space
$2^{[N]\setminus\\{i\\}}$ with the analogous transition rates and
$(\tilde{V}_{i})_{i}$ be the associated value functions. Observe that
$(\tilde{X}_{n})_{n}$ can be embedded in $(X_{n})_{n}$ via the identification

$\tilde{X}_{n}:=S\in 2^{[N]\setminus\\{i\\}}\ \text{ if and only if }\
X_{n}=S\,\text{ or }\,X_{n}=S\cup\\{i\\}$

yielding
$\displaystyle\tilde{V}_{j}(S)=\int_{\Omega}\sum_{n=1}^{\tau_{S}\wedge\tau_{S\cup\\{i\\}}}\mathrm{d}_{j}v(X_{n-1},X_{n})d{\cal
P}$ for all $j\in[N]\setminus\\{i\\}$. Now consider an arbitrary connected
finite path $\theta:X_{0}\to X_{1}\to\dots\to X_{n}$ on the hypercube graph
where $X_{0}=S$ and $X_{n}=S\cup\\{i\\}$, or $X_{0}=S\cup\\{i\\}$ and
$X_{n}=S$. Its reversed path is then given by
$\theta^{\prime}:X_{0}^{\prime}\to\dots\to X_{n}^{\prime}$ where
$X_{k}^{\prime}=X_{n-k}$. Finally flip the reversed path with respect to $i$
and get the path $\theta^{*}:X_{0}^{*}\to\dots\to X_{n}^{*}$, where
$X^{*}_{k}=S\in 2^{[N]\setminus\\{i\\}}$ if $X^{\prime}_{k}=S\cup\\{i\\}$ and
$X^{*}_{k}=S\cup\\{i\\}$ if $X^{\prime}_{k}=S$. Observe that the
correspondence $\theta\leftrightarrow\theta^{*}$ is bijective, both starts at
$S$ and ends at $S\cup\\{i\\}$ (or $S\cup\\{i\\}$ and $S$), and

$\sum_{k=1}^{n}\mathrm{d}_{j}v(X_{k-1},X_{k})=-\sum_{k=1}^{n}\mathrm{d}_{j}v(X^{*}_{k-1},X^{*}_{k})$

since $\mathrm{d}_{i}v=0$. Notice, in view of the path integral formula for
$V_{j}$, this implies

$\tilde{V}_{j}(S)=V_{j}(S)=V_{j}(S\cup\\{i\\}).$

Induction hypothesis gives $\tilde{V}_{j}(S)=\tilde{v}_{j}(S)$ where
$\tilde{v}$ is the restriction of $v$ on $2^{[N]\setminus\\{i\\}}$, and
moreover $\tilde{v}_{j}(S)=v_{j}(S)=v_{j}(S\cup\\{i\\})$ by Theorem 2.1. This
verifies A3.

Finally let us verify A5. For any states $S,T\subseteq[N]$, consider the
Markov chain $(X^{S}_{n})_{n}$ whose initial state is $X^{S}_{0}=S$ (instead
of $\emptyset$). Define analogously $\mathrm{D}^{S}_{i}v(T)$ and
$V^{S}_{i}(T)={\mathbb{E}}[\mathrm{D}^{S}_{i}v(T)]$ via $X^{S}$ in place of
$X$. By the correspondence between paths from $S$ to $T$ and their reverse
from $T$ to $S$, it readily follows $V^{S}_{i}(T)=-V^{T}_{i}(S)$. Now we prove
the following transition formula

(3.1) $V_{i}(T)-V_{i}(S)=V^{S}_{i}(T).$

To see this, we compute

$\displaystyle{\mathrm{D}}_{i}v(T)-{\mathrm{D}}_{i}v(S)$
$\displaystyle=\sum_{n=1}^{\tau_{T}}\mathrm{d}_{i}v\big{(}X_{n-1},X_{n}\big{)}-\sum_{n=1}^{\tau_{S}}\mathrm{d}_{i}v\big{(}X_{n-1},X_{n}\big{)}$
$\displaystyle={\bf
1}_{\tau_{S}<\tau_{T}}\sum_{n=\tau_{S}+1}^{\tau_{T}}\mathrm{d}_{i}v\big{(}X_{n-1},X_{n}\big{)}-{\bf
1}_{\tau_{T}<\tau_{S}}\sum_{n=\tau_{T}+1}^{\tau_{S}}\mathrm{d}_{i}v\big{(}X_{n-1},X_{n}\big{)}.$

By taking expectation, we obtain via the Markov property

$\displaystyle{\mathbb{E}}[{\mathrm{D}}_{i}v(T)]-{\mathbb{E}}[{\mathrm{D}}_{i}v(S)]={\cal
P}(\\{\tau_{S}<\tau_{T}\\})V^{S}_{i}(T)-{\cal
P}(\\{\tau_{T}<\tau_{S}\\})V^{T}_{i}(S)=V^{S}_{i}(T)$

which proves (3.1). Now for any $S,T\subseteq[N]\setminus\\{i\\}$, we observe

$\displaystyle
V_{i}(T\cup\\{i\\})-V_{i}(S\cup\\{i\\})=V^{S\cup\\{i\\}}_{i}(T\cup\\{i\\})=-V^{S}_{i}(T)=-\big{(}V_{i}(T)-V_{i}(S)\big{)}$

where the middle equality stems from the correspondence of reflected paths
with respect to $i$ given in the discussion (iv) in the previous section. This
verifies A5. ∎

A recent work of Lim [14] discusses this theorem in more general graph
settings.

## References

  * Candogan et al. [2011] O. Candogan, I. Menache, A. Ozdaglar, and P. A. Parrilo, _Flows and decompositions of games: harmonic and potential games_ , Math. Oper. Res., 36 (2011), pp. 474–503.
  * Castro et al. [2017] J. Castro, D. Gómez, E. Molina, and J. Tejada, _Improving polynomial estimation of the Shapley value by stratified random sampling with optimum allocation_ , Comput. Oper. Res., 82 (2017), pp. 180–188.
  * Castro et al. [2009] J. Castro, D. Gómez, and J. Tejada, _Polynomial calculation of the Shapley value based on sampling_ , Comput. Oper. Res., 36 (2009), pp. 1726–1730.
  * Deng and Papadimitriou [1994] X. T. Deng and C. H. Papadimitriou, _On the complexity of cooperative solution concepts_ , Math. Oper. Res., 19 (1994), pp. 257–266.
  * Faigle and Kern [1992] U. Faigle and W. Kern, _The Shapley value for cooperative games under precedence constraints_ , Internat. J. Game Theory, 21 (1992), pp. 249–266.
  * Hodge [1941] W. V. D. Hodge, _The Theory and Applications of Harmonic Integrals_ , Cambridge University Press, England; Macmillan Company, New York, 1941.
  * Jiang et al. [2011] X. Jiang, L.-H. Lim, Y. Yao, and Y. Ye, _Statistical ranking and combinatorial Hodge theory_ , Math. Program., 127 (2011), pp. 203–244.
  * Kalai and Samet [1987] E. Kalai and D. Samet, _On weighted Shapley values_ , Internat. J. Game Theory, 16 (1987), pp. 205–222.
  * Khmelnitskaya et al. [2016] A. Khmelnitskaya, O. Selçuk, and D. Talman, _The Shapley value for directed graph games_ , Oper. Res. Lett., 44 (2016), pp. 143–147.
  * Kodaira [1949] K. Kodaira, _Harmonic fields in Riemannian manifolds (generalized potential theory)_ , Ann. of Math. (2), 50 (1949), pp. 587–665.
  * Koshevoy et al. [2017] G. Koshevoy, T. Suzuki, and D. Talman, _Cooperative games with restricted formation of coalitions_ , Discrete Appl. Math., 218 (2017), pp. 1–13.
  * Kultti and Salonen [2007] K. Kultti and H. Salonen, _Minimum norm solutions for cooperative games_ , Internat. J. Game Theory, 35 (2007), pp. 591–602.
  * Lim [2020] L.-H. Lim, _Hodge Laplacians on graphs_ , SIAM Rev. 62 (2020), no. 3, 685–715.
  * Lim [2021] T. Lim, _Hodge theoretic reward allocation for generalized cooperative games on graphs_ , arXiv preprint.
  * Peters [2008] H. Peters, _Game theory. A multi-leveled approach._ Springer-Verlag, 2008.
  * Roth [1977] A.E. Roth, _The Shapley Value as a von Neumann-Morgenstern Utility_ , Econometrica, 45 (1977), pp. 657–664.
  * Roth [1988] A.E. Roth, _A.E Roth (Ed.), The Shapley Value: Essays in Honor of Lloyd S. Shapley_ , Cambridge Univ. Press, New York (1988).
  * Ruiz et al. [1998] L. M. Ruiz, F. Valenciano, and J. M. Zarzuelo, _The family of least square values for transferable utility games_ , Games Econ. Behav., (1998) 109–130.
  * Shapley [1953a] L. S. Shapley, _Additive and non-additive set functions_ , ProQuest LLC, Ann Arbor, MI, 1953a. Thesis (Ph.D.)–Princeton University.
  * Shapley [1953b] L. S. Shapley, _A value for $n$-person games_, in Contributions to the theory of games, vol. 2, Annals of Mathematics Studies, no. 28, 1953b, pp. 307–317.
  * Shapley [1953c] L. S. Shapley, _Stochastic games_ , Proc. Nat. Acad. Sci. 39 (1953), 1095–1100.
  * Shapley [2010] L. S. Shapley, _Utility comparison and the theory of games_ (reprint), Bargaining and the theory of cooperative games: John Nash and beyond, 235–247, Edward Elgar, Cheltenham, 2010.
  * Stern and Tettenhorst [2019] A. Stern and A. Tettenhorst, _Hodge decomposition and the Shapley value of a cooperative game_ , Games and Economic Behavior,113 (2019) 186–198.