# Strong tournaments

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?

• Is this an excercise from a book? You should give a reference wher you get your question from. Jul 29, 2019 at 10:58
• @András, Actually it is not from a book. Do you have an idea on how to solve it? Jul 29, 2019 at 17:27
• You seem to be using $E$ for an enumeration of the vertices, and also for the set of directed edges. Aug 4, 2019 at 16:48
• Yes you're right I'll change that Aug 4, 2019 at 16:49
• Case 3: $(v_1,v_n)\in E(C)$. Then there is $1<i<n$ such that $(v_i,v_1)\in E(C)$. When computing $i_N(C)$, $(v_1,v_n)$ contributes $+0$ and $(v_i,v_1)$ contributes $+1$. When computing $i_{N'}(C)$, $(v_1,v_n)$ and $(v_i,v_1)$ both contribute $+0$. The rest of the edges in $C$ contribute the same counts to $i_{N}(C)$ and $i_{N'}(C)$ since they do not involve $v_1$. So $i_{N'}(C)=i_{N}(C)-1$. Oct 28, 2019 at 14:27

As you suspected, taking a better enumeration suffices. 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$$.
• How about if $v_1$ was connected to all the other vertices by a forward edge? I mean $(v_1,v_2), (v_1,v_3), (v_1,v_4) ... \in E(C)$ ? Then they will all be back edges in your enumeration Oct 8, 2019 at 14:01
• Note that any circuit $C$ that contains $v_1$ but not $(v_1,v_n)$ will contain the edges $(v_i,v_1), (v_1,v_j)$ for some $i,j>1$. Oct 8, 2019 at 14:14