Strong tournaments

Question

Let $T$ be a strong tournament, and let $N=v_1v_2 \cdots v_n$ be an enumeration of $V(T)$. Let $C$ be a circuit in $T$. We define $i_N(C)=|\{(v_i,v_j) \in E(C); i>j\}|$. Suppose that $N$ is chosen in such a way that $i_N(C_1)+ \cdots + i_N(C_t)$ is minimum, where $C_1, \cdots, C_t$ are all the circuits of $T$.

Prove that $\forall i$ such that $1 \le i \le n-1$, $(v_i,v_{i+1}) \in E(T)$ and that $(v_n,v_1) \in E(T)$.

My attempt:

I already proved that $\forall i$ such that $1 \le i \le n-1$ we have $(v_i,v_{i+1})\in E(T)$.

I first assumed that $(v_i,v_{i+1}) \not \in E(T)$, and this gives that $(v_{i+1},v_{i})\in E(T)$, so I took the enumeration $N'=v_1 \cdots v_{i-1}v_{i+1}v_iv_{i+2} \cdots v_n$, and proved that $i_{N'}(C_1)+ \cdots + i_{N'}(C_t)< i_N(C_1)+ \cdots + i_N(C_t)$, which is a contradiction.

But for proving $(v_n,v_1) \in E(T)$ I supposed that $(v_1,v_n) \in E(T)$ and tried to take the enumeration $N''=v_nv_1\cdots v_{n-1}$ but I wasn't able to get to a contradiction, since to get to a contradiction from this enumeration I must be sure that the number of forward edges going to $v_n$ was less than that of the backward edges from $v_n$ in the first enumeration, can I prove this?Or do I take 2 cases if the number of forward edges was less or more than that of the backward edges? Or is there another enumeration that can finish it?

Please help, and thanks in advance.

Answer 1

If $(v_n,v_1)\not\in E$ then consider the enumeration $N'=(v_2,v_3,\cdots,v_{n-1},v_1,v_n)$. It is easy to see that for any circuit $C$ such that $(v_1,v_n)\not\in E(C)$ we have $i_N(C)=i_{N'}(C)$. For any circuit $C$ such that $(v_1,v_n)\in E(C)$ (and there is one since $T$ is strong) we get $i_{N'}(C)=i_N(C)-1$, contradicting our assumption on $N$.

Answer 2

hmm I think what you can do is if $v_1 v_n$ is directed towards $v_n$, then consider reversing it and all other backwards arcs Consider a circuit in this digraph $T'$ (all edges forward except $v_1,v_n$ ) each such circuit consists of a path $P$ from $v_1$ to $v_n$ and back from $v_n$ to $v_1$ Let $Q$ be a path from $v_n$ to $v_1$ in $T$ If $P$ consists not entirely of edges directed backwards in $T$, then $P \cup Q$ is a closed walk in $T$ where some edges appear only once and hence contains a cycle. Otherwise$ P \cup v_1v_n$ is a cycle in $T$ Also there is at least 1 path $P$ which uses 2 backward edges of $T$ and thus the tournament $T'$ has smaller value contradiction