Proving that every strongly connected tournament T on at least 4 vertices contains distinct vertices u, v such that T-u and T-v are strongly connected

Question

I have a two part question:

1. Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected?
   (In fact, I will give a simple proof of this below as a corollary of Theorem 1, but what I'm interested in is a proof which does not use Theorem 1 and is perhaps analogously as simple as the proof that every connected graph $G$ on $n\geq 2$ vertices contains distinct $u,v\in V(G)$ such that $G-u$ and $G-v$ are connected.)

2. For all $n\geq 4$ there exists a strongly connected tournament $T^*:=T^*_n$ on $n$ vertices having only two vertices $u,v$ such that $T^*-u$ and $T^*-v$ are strongly connected. Let $V(T^*)=\{v_1, \dots, v_n\}$ and $E(T^*)=\{(v_{i+1}, v_{i}): i\in [n-1]\}\cup \{(v_i, v_j): 1\leq i\leq j-2\leq n-2\}$ (in other words $T^*$ is a transitive tournament in which we reverse the direction of the edges along the path $v_1v_2\dots v_n$). Note that for all $2\leq i\leq n-1$, $T^*-v_i$ is not strongly connected.
   Is $T^*_n$ the unique tournament with this property? That is, if $T$ is a strongly connected tournament on $n\geq 4$ vertices having exactly two vertices $u,v$ such that $T-u$ and $T-v$ are strongly connected is $T\simeq T^*_n$?
   I used sage/nauty to confirm this for all $4\leq n\leq 10$. Also does $T^*_n$ have any particular name in the literature?

Theorem 1 Every strongly connected tournament $T$ on $n\geq 3$ vertices has the property that for all $3\leq k\leq n$ and all $v\in V(T)$, there exists a cycle of length $k$ containing $v$.

For a proof of this fact see Theorem 3 on Page 7 of Moon - Topics on Tournaments).

Corollary Every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected.

Proof. Let $C$ be a cycle of length $n-1$ and let $u\in V(T)\setminus V(C)$. Now let $C'$ be a cycle of length $n-1$ which contains $u$ and let $v\in V(T)\setminus V(C')$. So $u$ and $v$ are the desired vertices.

Answer 1

I'll give a (somewhat messy) proof of the uniqueness statement in (2.) using the notion of a (directed) ear decomposition. In particular, I will use the fact that a directed graph is strongly connected if and only if it has such a decomposition, and that in this case we can find an ear decomposition starting with any directed cycle.

First, suppose that there is an arc $uv$ in $T$ such that every other arc incident to $u$ is ingoing and every other arc incident to $v$ is outgoing. Then for any vertex $w \neq u,v$, $T-w$ is strongly connected. For $n \geq 5$, this gives at least $3$ vertices that we can delete; for $n = 4$, $T$ is isomorphic to $T^*$.

Now suppose that there is no such arc in $T$. You have already shown that there are vertices $u,v$ such that both $T-u$ and $T-v$ are strongly connected. By your Theorem 1, $T$ contains a Hamiltonian cycle $C_0$. We shall consider two cases:

1. There is a cycle $C$ other than $C_0$ that contains both $u$ and $v$.
2. There is no such cycle.

In the first case, we can find a third vertex that we can delete from $T$ while retaining strong connectivity. Indeed, since $T$ is strongly connected, it has a directed ear decomposition $C,P_1,\dots,P_m$, where each $P_i$ is a path whose starting and ending vertices are in $C \cup \bigcup_{j < i} P_j$ and its inner vertices are disjoint from it. We may assume that the last ear $P_m$ has length at most $3$, since otherwise we can shortcut it. Moreover, if it has length $3$ and we cannot shortcut it, then the two inner nodes must form the kind of vertex pair that we have dealt with at the beginning of the proof. So by shortcutting we may assume that $P_m$ has length $2$ and so is of the form $u_0wv_0$. Then $T-w$ is strongly connected, since it has an ear decomposition $C,P_1,\dots,P_{m-1}$.

Finally, we deal with the second case by showing that it implies $T \simeq T^*$. We may suppose that $uv$ is an arc of $T$. There is a path $P$ in $T$ from $v$ to $u$, which gives us a cycle $P + uv$. By our assumption this can only be the Hamiltonian cycle $C_0$, so we get that the latter is of the form $v = v_0, v_1, \dots, v_n = u$. If there were another "forward arc" in $T$, we could shortcut $C_0$ to obtain a shorter cycle containing $u$ and $v$, a contradiction. So every other arc must point backward, which shows that $T$ is just $T^*$.

---

A similar idea can be used to give a proof of (1.) that avoids Theorem 1 as follows: the first case (when there is a "special" arc $uv$) is the same as before. If there is no such arc, any ear decomposition can be shortcut so that the last ear has a single inner vertex. Taking an arbitrary ear decomposition, this gives a vertex $u$ that can be removed; then starting from a cycle that contains $u$ and taking another ear decomposition, we get another such vertex. We should show that there is indeed a cycle containing $u$ that is not a Hamiltonian cycle, but this is considerably easier than Theorem 1.

Granted, in this case you have to rely on the fact that the existence of an ear decomposition is equivalent to being strongly connected, and it is (at the very least) questionable whether this proof is "simpler" than yours. On the other hand, it does somewhat mirror the undirected case, where instead of spanning trees (which characterize connected graphs) we use ear decompositions (which characterize strongly connected directed graphs), and instead of leaves we use "minimal ears".

Answer 2

After reading relep's answer I revisited the problem and came up with a different fairly simple proof for Question 1, but before I get to that, I recently found that this problem has a long history already (the key phrase that led me to these references was "non-critical vertex"). It turns out that in 1966 Korvin asked exactly my Question #1 (G. Korvin, Some combinatorial problems on complete directed graphs) Then in 1972, Rao and Rao solved the problem raised by Korvin (see Section 2 of S. B. Rao, A. R. Rao, The number of cut vertices and cut arcs in a strong directed graph). According to D. Meierling and L. Volkmann, On the number of nonseparating vertices in strongly connected local tournaments, Las Vergnas answered Question #2 in the affirmative in 1975, (M. Las Vergnas, Sur le nombre de circuits dans un tournoi fortement connexe), but in 1989 Thomassen also answered Question #2 in the affirmative and while he cites the Las Vergnas paper, he doesn't attribute that result to Las Vergnas (C. Thomassen, Whitney’s 2-switching theorem, cycle spaces, and arc mappings of directed graphs). Since the Las Vergnas paper is in French and I don't even have easy access to it, I won't be getting to the bottom of that just yet.

As for Rao and Rao's solution to Question #1, there is actually something about their proof that I don't understand. They prove it in the more general setting of semi-complete digraphs and their proof easily shows that if $T$ has some vertex $v$ such that $T-v$ is strongly connected, then $T$ has at least two such vertices. But there seems to be an oversight in the proof that $T$ has at least one such vertex. It has to do with the sentence "Since $G$ is maximal, $x$ is a non-cut vertex of $G_1$." While adding the edge $(y,z)$ "converts some cut vertex into a non-cut vertex," I don't see why that vertex must be $x$.

Finally, here is my different proof of Question 1. Let's call a vertex $v$ in a strongly connected digraph non-critical if $T-v$ is strongly connected and critical otherwise.

Lemma 1 If $T$ is a tournament on $n\geq 4$ vertices with diameter $2$, then $T$ has at least $n-2$ non-critical vertices.

Proof. If every vertex is non-critical we are done, so suppose $v$ is critical vertex. This implies that $T-v$ has at least two strongly connected components. Suppose $T-v$ has $k\geq 3$ strongly connected components, $T_1$, $\dots$, $T_k$ with all edges oriented from $T_i$ to $T_j$ for all $i<j$. For all $i\in [3]$, let $x_i\in T_i$. Since $T$ has diameter 2, there is a path of length 2 from $x_3$ to $x_2$ which must go through $v$ and there is a path of length 2 from $x_2$ to $x_1$ which also must go through $v$, but this is impossible as it would mean that $(x_2,v)$ and $(v, x_2)$ are edges. So $T-v$ has exactly two strongly connected components $T_1$ and $T_2$ with all edges going from $T_1$ to $T_2$. Furthermore, all edges from $v$ to $T_1$ and all edges from $T_2$ to $v$. If $T_i$ has at least two vertices, then every vertex in $T_i$ is non-critical. Since $n\geq 4$, at least one of $T_1$ or $T_2$ has at least two vertices.$\square$

Say that an $x,y$-path $P$ in a digraph $D$ is a maximal short path if $P$ is the shortest path from $x$ to $y$ and there is no other shortest path between two vertices containing $P$ as a segment

Lemma 2 Let $T$ be a tournament on $n\geq 4$ vertices. If $P$ is a maximal short path of length at least 3 with endpoints $x$ and $y$, then $x$ and $y$ are non-critical vertices.

Proof. Let $x,y\in V(T)$ and $P$ as given in the statement. Suppose for contradiction that, say $T-y$ is critical and let $u$ and $v$ be vertices in $T-y$ such that every $u,v$-path goes through $y$. Note that $u$ and $v$ can be chosen so that the distance between $u$ and $v$ is exactly 2. There must be a path from $x$ to $v$ in $T-y$, otherwise the shortest path from $x$ to $v$ would contain $P$. This implies that $(u,x)$ is not an edge; i.e. $(x,u)$ is an edge. But then the distance from $x$ to $y$ is at most 2, contradicting the assumption.$\square$

Theorem 1 If $T$ is a tournament on $n\geq 4$ vertices, then $T$ has at least two non-critical vertices.

Proof. Let $d$ be the diameter of $T$. If $d=2$, we are done by Lemma 1 and if $d=n-1$, then $T\simeq T^*_n$; so suppose $3\leq d\leq n-2$. Let $x$ and $y$ be vertices which witness the fact that the diameter is $d$ and let $P$ be the path from $x$ to $y$. By Lemma 2, $x$ and $y$ are non-critical. $\square$

I feel that this proof should be able to also answer Question 2, but I don't see how at the moment. I originally thought I saw a way forward, but my initial idea didn't work out.