length of a path that passes through at least one vertex of each (elementary) circuit of a strong connected directed graph

Question

Let $G$ be strongly connected directed graph with vertex set $\{1, 2, \ldots, n\}$. A circuit $i_0=i, i_1, \ldots, i_n=i$ is elementary if path $ i_1, \ldots, i_{n-1}$ is a path in which no vertex appears more than once.

In a paper, author claims that if the length of any elementary circuit of $G$ is larger than or equal to 2, then there is a set $S=\{i_1,_2,\ldots, i_m\}\subseteq \{1, 2, \ldots n\}$ with $m\leq [\frac{n}{2}]+1$ such that any elementary circuit of $G$ contains at least one vertex that belongs to $S$.

I do not know proof of it. Can you please help me to know it?

Indeed proof of the following lemme is not clear for me.

Lemma. Let $G$ be strongly connected directed graph with vertex set $\{1, 2, \ldots, n\}$ and the length of any elementary circuit of $G$ is larger than or equal to 2. If $i,j\in\{1, \ldots n\}$, then there exists a (possibly empty) path $P_{ij}$ from $j$ to $i$ in $G$ that passes through at least one vertex of each (elementary) circuit of $G$ and that has a length that is less than or equal to $\frac{n^2-1}{2}$.

Answer 1

Maybe I am misunderstanding something in your notation but I think the result you require is false:-

Consider a graph with, say, $6$ vertices such that each pair of vertices is joined in each direction. Then, for any pair of vertices $i,j$, there is an elementary circuit $iji$.

Therefore $S$ has to include at least one of every pair of vertices and so $|S|\ge 5$.

Answer 2

Even if the shortest elementary circuit allowed is a three-vertex circuit, then the claim is false (and very far from true).

Consider a random tournament: for each pair $\{i,j\}$, flip a coin to determine whether $G$ will have the directed edge $i \to j$ or $j \to i$. Then:

• With high probability, $G$ is strongly connected. For any set of vertices $S$, the probability is $2^{-|S| \cdot (n-|S|)}$ that all edges between $S$ and $V-S$ are oriented out of $S$, so the probability that $G$ is not strongly connected is at most $$\sum_{1 < |S| < n} 2^{-|S| \cdot (n-|S|)} = \sum_{k=1}^{n-1} \binom nk 2^{-k(n-k)} \le \binom n1 2^{1-n} + \sum_{k=2}^{n-2} \binom nk 2^{-2(n-2)} +\binom n{n-1}2^{1-n} \le \frac{4n+16}{2^n}$$ which decays very quickly with $n$.
• With high probability, $G$ has no transitive subtournament of size $t = 2\log_2 n+2$ (or larger). The expected number of such tournaments is $$\binom nt \cdot t! \cdot 2^{-t(t-1)/2} \le n^t 2^{-t(t-1)/2} = 2^{t(t-2)/2} \cdot 2^{-t(t-1)/2} = 2^{-t/2} = \frac1{2n}.$$

In particular, we can choose $G$ to satisfy both properties (assuming $\frac{4n+16}{2^n}+\frac{1}{2n}<1$, which happens when $n\ge 6$).

For any set $S$ of fewer than $n-t$ vertices, the complement of $S$ will not form a transitive tournament, and therefore there will be a cycle, none of whose vertices are in $S$. So when $n$ is large, you can't get away with a set $S$ of size $\lfloor \frac n2 \rfloor + 1$: you need a set $S$ of size almost $n$.