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$ Commented Jul 29, 2019 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$ Commented Jul 29, 2019 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$ Commented Aug 4, 2019 at 16:48
  • 1
    $\begingroup$ Yes you're right I'll change that $\endgroup$ Commented Aug 4, 2019 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$ Commented Oct 28, 2019 at 14:27

1 Answer 1

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$ Commented Oct 7, 2019 at 14:52
  • $\begingroup$ There can be more than 1. What I meant to say was there is at least one. $\endgroup$ Commented Oct 8, 2019 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$ Commented Oct 8, 2019 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$ Commented Oct 8, 2019 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$ Commented Oct 8, 2019 at 15:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .