7
$\begingroup$

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.

$\endgroup$
12
  • 3
    $\begingroup$ Is this an excercise from a book? You should give a reference wher you get your question from. $\endgroup$ – András Bátkai Jul 29 '19 at 10:58
  • 1
    $\begingroup$ @András, Actually it is not from a book. Do you have an idea on how to solve it? $\endgroup$ – Fareed Abi Farraj Jul 29 '19 at 17:27
  • 1
    $\begingroup$ You seem to be using $E$ for an enumeration of the vertices, and also for the set of directed edges. $\endgroup$ – Gabe Conant Aug 4 '19 at 16:48
  • 1
    $\begingroup$ Yes you're right I'll change that $\endgroup$ – Fareed Abi Farraj Aug 4 '19 at 16:49
  • 1
    $\begingroup$ 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$. $\endgroup$ – Gabe Conant Oct 28 '19 at 14:27
4
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ Why there is only 1? Is the only circuit you're talking about the one passing through all the vertices? How can we prove that? $\endgroup$ – Fareed Abi Farraj Oct 7 '19 at 14:52
  • $\begingroup$ There can be more than 1. What I meant to say was there is at least one. $\endgroup$ – Erlang Wiratama Surya Oct 8 '19 at 13:33
  • $\begingroup$ 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 $\endgroup$ – Fareed Abi Farraj Oct 8 '19 at 14:01
  • $\begingroup$ 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$. $\endgroup$ – Erlang Wiratama Surya Oct 8 '19 at 14:14
  • $\begingroup$ You mean I was wrong by saying "...all..."? Or is it something else that you mean it? But even if they weren't all forward, how can we know that the number of forward edges was more than the number of backward edges in the first enumeration?(Because if this is right then it is done by the enumeration you've given) Maybe I didn't get your point exactly, please explain it more to me. $\endgroup$ – Fareed Abi Farraj Oct 8 '19 at 15:48

Your Answer

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

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