Proof. Let \(T\) be a 2-arc-strong tournament with \(\delta^0(T)\geq K\) and let \(x\) be a vertex of \(T\). Let \(D=(V,A)\) be the digraph that we obtain from 4 disjoint copies \(T_i\), \(i\in [4]\), of \(T\) by adding the arcs of the 4-cycle \(x_1x_3x_2x_4x_1\), the arcs \(x_1x_2,x_3x_4\), all possible arcs from \(V(T_2)\) to \(V(T_1)\) and from \(V(T_4)\) to \(V(T_3)\). Here \(x_i\) is the copy of \(x\) in \(T_i\). See Figure 1. Then \(D\) is co-bipartite and 2-arc-strong and we claim that \(D'\) does not contain a pair of arc-disjoint spanning strong subdigraphs.

Indeed, suppose there is a partition \(A=A_1\cup A_2\) such that \(D_i=(V,A_i)\) is strong for \(i=1,2\). There are exactly two arcs in \(D\) in both directions between \(V(T_1)\cup V(T_2)\) and \(V(T_3)\cup V(T_4)\). Without loss of generality we have \(x_4x_1\in A_1\) and \(x_3x_2\in A_2\). As there are only two arcs entering \(V(T_2)\), this implies that the arc \(x_1x_2\) must be in \(A_1\) (in order to reach the vertices in \(V(T_2)\)) and as there are only two arcs leaving \(V(T_1)\) we have \(x_1x_3\in A_2\). We must also have \(x_3x_4\in A_1\), since the only other arc leaving \(V(T_3)\) is in \(A_2\). This implies that the arc \(x_2x_4\) must be in \(A_2\) now we see that there is no path from \(V(T_1)\cup V(T_2)\) to \(V(T_3)\cup V(T_4)\) in \(D_1\), contradiction. ◻

Proof. Let \(D\) have \(\alpha{}(D)=2\). By Theorem 17 \(D\) has a hamiltonian cycle or it has two cycles \(C_1,C_2\) that cover \(V(D)\) and whose intersection is a (possibly empty) subpath of both cycles. If \(D\) has a hamiltonian cycle we take \(S\) to be that cycle and we are done as (B1) holds. So now assume that \(D\) contains no hamiltonian cycle, which by Theorem 17 implies that \(D\) contains two cycles \(C_1,C_2\) that cover \(V(D)\) and whose intersection is a (possibly empty) subpath of both cycles. Let such \(C_1\) and \(C_2\) be chosen such that \(|V(C_1)\cap V(C_2)|\) is maximum possible.

We now consider the case when \(|V(C_1)\cap V(C_2)|>0\). If \(|V(C_1)\cap V(C_2)|=1\), then let \(x\) be the vertex in \(V(C_1)\cap V(C_2)\) and let \(A(S)\) to be the union of \(A(C_1)\) and \(A(C_2)\). Now the first part of (B3) holds. If \(N_S^+(x)\) is not an independent set, then without loss of generality assume that \(xu \in A(C_1)\) and \(xv \in A(C_2)\) and \(uv \in A(D)\). Now remove the arc \(xv\) from \(C_2\) and add the path \(xuv\), in order to obtain a new cycle \(C_2'\), with \(|V(C_1)\cap V(C_2')|=2>1=|V(C_1)\cap V(C_2)|\), and thereby contradicting the maximality of \(|V(C_1)\cap V(C_2)|\). Therefore \(N_S^+(x)\) is an independent set. We can analogously show that \(N_S^-(x)\) is an independent set, and therefore part (B3) holds. This completes the case when \(|V(C_1)\cap V(C_2)|=1\). We may therefore assume that \(|V(C_1)\cap V(C_2)|\geq 2\). That is, there are vertices \(x,y\in V(C_1)\cap V(C_2)\) such that the path common to \(C_1\) and \(C_2\) is \(P\) and \(P=C_i[x,y]\) for \(i=1,2\). Now the first part of (B2) holds. If \(N_S^+(y)\) is not an independent set then analogously to above we get a contradiction to the maximality of \(|V(C_1)\cap V(C_2)|\) (or to \(D\) not being hamiltonian). And, again analogously to above, we can show that \(N_S^-(x)\) is also an independent set. Therefore (B2) holds in this case. This completes the case when \(|V(C_1)\cap V(C_2)|>0\).

Now assume that \(|V(C_1)\cap V(C_2)|=0\) and therefore \(C_1\) and \(C_2\) are vertex disjoint. As \(D\) is strongly connected there exists a \((C_1,C_2)\)-arc, say \(x_1 x_2 \in A(D)\). Let \(x_1^+\) be the successor of \(x_1\) on \(C_1\). If there is any \((C_2,x_1^+)\)-arc, \(y_2 x_1^+\), in \(D\), then considering the cycle \(C_1[x_1^+,x_1] C_2[x_2,y_2] x_1^+\) instead of \(C_1\), would contradict the maximality of \(|V(C_1)\cap V(C_2)|\). So there is no \((C_2,x_1^+)\)-arc in \(D\). If there is an \((x_1^+,C_2)\)-arc in \(D\), then consider \(x_1^+\) instead of \(x_1\). Continuing this process either gives us a vertex which is not adjacent to any vertex in \(C_2\) or there is no arc from \(C_2\) to \(x_1\), \(x_1^+\), \(\left(x_1^+\right)^+\), etc., a contradiction to \(D\) being strong. So there must be a vertex \(u_1 \in V(C_1)\) which is not adjacent to any vertex in \(C_2\).

Analogously we can show that there must be a vertex \(u_2 \in V(C_2)\) which is not adjacent to any vertex in \(C_1\). This implies that \(D[V(C_i)]\) is semicomplete, as if two vertices, \(x_i,y_i\), in \(D[V(C_i)]\) are non-adjacent then \(\{x_i,y_i,u_{3-i}\}\) is an independent set, a contradiction to \(\alpha(D)=2\).

3 Non-separating out-branchings in semicomplete digraphs↩︎

Proof. Recall that in an out-branching every vertex except the root has one arc entering it. Hence if a vertex has in-degree one in \(D\), it must be the root of any non-separating out-branching. This shows that if \(D\) admits a non-separating out-branching, it has at most one vertex with in-degree one. This proves the first part of (a).

Now assume that \(D\) contains exactly two vertices, \(r_1\) and \(r_2\), with in-degree one and let \(H\) be a hamiltonian cycle in \(D\) (\(H\) exists by Theorem 10) and let \(D'=D\setminus{}A(H)\). If there is only one initial strong component in \(D'-r_2\), then letting \(T^+\) be an out-branching in \(D'-r_2\) gives us the desired out-tree. So assume that there are at least two initial strong components in \(D'-r_2\), \(\{r_1\}\) and \(S_1\). If \(|V(S_1)| \geq 2\) then as \(r_1\) is non-adjacent to \(\{r_2\} \cup V(S_1)\) in \(D'\) and \(|\{r_2\} \cup V(S_1)| \geq 3\) we obtain a contradiction (as \(H\) was a hamiltonian cycle, meaning that we removed only 2 arcs incident to \(r_1\) when we obtained \(D'\) from \(D\)). So \(|S_1|=1\) and we let \(V(S_1)=\{t_1\}\). As \(d_D^-(t_1) \geq 2\), we have \(d_{D'}^-(t_1) =1\) and \(N_{D'}^-(t_1) = \{r_2\}\). Analogously considering \(D'-r_1\) instead of \(D'-r_2\) we obtain an initial strong component \(S_2\) in \(D'-r_1\) where \(V(S_2)=\{t_2\}\) and \(N_{D'}^-(t_2) = \{r_1\}\). Note that \(t_1 \not= t_2\) (as \(r_1t_2,r_2t_1 \in A(D')\)). Furthermore \(t_1\) and \(t_2\) are not adjacent in \(D'\), as if \(t_1 t_2 \in A(D')\) then \(r_2 t_1 t_2\) is a path in \(D'-r_1\) and \(S_2\) is not an initial strong component in \(D'-r_1\). So in \(D'\), \(r_1\) is non-adjacent to \(\{r_2,t_1\}\) and \(t_2\) is non-adjacent to \(\{r_2,t_1\}\). Therefore \(|V(D)|=4\) and \(D\) is isomorphic to \(W_2\). This proves the second part of (a).

It is easy to check that if \(D\) is the semicomplete digraph \(W_1\) in Figure 3, then every out-branching is separating (the vertex \(p_1\) with in-degree one must be the root of all out-branchings), which proves part (b).

Now suppose that \(D=(V,A)\) is different from \(W_1\) and has exactly one vertex of in-degree one, which implies that \(n=|V(D)| \geq 3\). Let \(H=p_1 p_2 \ldots p_n p_1\) be a hamiltonian cycle in \(D\) and let \(D'=D\setminus{}A(H)\). Without loss of generality assume that \(d_D^-(p_1)=1\), which implies that \(d_{D'}^-(p_1)=0\). If \(D'\) only has one initial strong component, then \(D'\) contains an out-branching, \(B_{p_1}^+\), rooted at \(p_1\), which implies that \(B_{p_1}^+\) is a non-separating out-branching in \(D\). Therefore we may assume that \(D'\) contains at least two initial strong components, one of which is just the vertex \(p_1\). As \(d_{D'}^-(x) \geq 1\) for all \(x \in V(D') \setminus \{p_1\}\) we note that any other initial strong component, \(S\), in \(D'\) must contain at least two vertices. Furthermore as there is no arc between \(p_1\) and the vertices in \(S\) in \(D'\), we must have \(V(S)=\{p_2,p_n\}\) and \(p_2 p_n, p_n p_2 \in A(D')\). Therefore \(n \geq 4\), as otherwise \(p_2 p_3 \in A(H)\) and \(p_2 p_3 \in A(D')\), a contradiction.

If \(n=4\), then we note that \(D=W_1\), a contradiction (as \(H=p_1p_2p_3p_4p_1\) and \(A(D') = \{p_2p_4,p_4p_2,p_1p_3\}\)). So assume that \(n \geq 5\). Let \(T\) be obtained from \(H\) by deleting the arc \(p_1p_2\) and adding the arcs \(p_np_2\) and \(p_1 p_3\). Note that \(T\) is a strongly connected spanning subgraph of \(D\). Let \(D^*=D\setminus{}A(T)\), and note that \(p_1 p_i \in A(D^*)\) for all \(i \in [n] \setminus \{n,3\}\) and \(p_1 p_2, p_2 p_n, p_n p_3 \in A(D^*)\) (as the vertex set of the initial component, \(S\), in \(D'\) was \(\{p_2,p_n\}\)). Therefore the only initial component in \(D^*\) is \(\{p_1\}\) and there exists an out-branching, \(B_{p_1}^+\) in \(D^*\) rooted at \(p_1\), which is therefore a non-separating branching in \(D\). This proves part (c).

We now consider the case when \(\delta^-(D)\geq 2\). If \(n \leq 3\), then \(D\) is the complete digraph on three vertices and part (d) holds. So assume that \(n \geq 4\). By Proposition 14, \(D\) admits a nice decomposition \((S_1,S_2,\ldots,S_p)\).

First consider the case when \(p=1\). That is \(D\) is \(2\)-arc-strong. If \(D\) is isomorphic to \(S_4\) (see Theorem 15), then as can be seen in Figure 4, \(S_4\) has a non-separating branching \(B^+_{r}\) for each \(r \in V(S_4)\). So we may assume that \(D\) is not isomorphic to \(S_4\), which by Theorem 15 implies that \(D\) contains two arc disjoint strong spanning subdigraphs \(D_1\) and \(D_2\). For every \(r \in V(D)\) we note that \(D_1\) contains an out-branching rooted at \(r\) and therefore \(D\) contains a non-separating branching, rooted at \(r\). This proves part (e) when \(p=1\).

We now consider the case when \(p \geq 2\). Let \(r \in S_1\) be arbitrary. Let \(st\) be the \((V(D)\setminus V(S_1),V(S_1))\)-arc in \(D\). That is, \(st\), is the cut-arc entering \(S_1\).

Construct a new digraph \(H_r\) from \(S_1\) by adding a vertex \(x\) to \(S_1\) and adding the two arcs \(x t\) and \(x r\) (if \(t=r\) we add two parallel arcs). We will first show that \(x\) has two arc-disjoint paths to every other vertex in \(H_r\). As \(S_1\) is strong we note that \(x\) can reach all other vertices in \(H_r\) if we delete \(x t\) or \(x r\). Furthermore if we delete any arc \(e \in A(S_1)\) then \(x\) can still reach all other vertices in \(S_1\) by starting with the arc \(x t\), as \(t\) can reach all other vertices in \(S_1\) even after deleting one arc (by the definition of a nice decomposition). By Theorem 1 this implies that there exists two arc-disjoint out-branchings both rooted in \(x\) in \(H_r\). Deleting \(x\) from these gives us two arc-disjoint out-branchings \(B_{t}^+, B^+_r\) in \(S_1\), rooted at \(t\) and \(r\), respectively.

We will now show that we may assume that \(B_t^+\) is not just an out-star rooted at \(t\). Assume that \(B_t^+\) is an out-star rooted at \(t\). We first consider the case when \(|S_1| \geq 4\). Let \(l_1,l_2,\ldots,l_{|S_1|-1}\) be the leaves of \(B_t^+\) and note that \(\{l_1,l_2,\ldots,l_{|S_1|-1}\}\) is not independent in \(D\setminus{}A(B_r^+)\) as the underlying graph of \(B_r^+\) is acyclic. So without loss of generality we may assume that \(l_1l_2 \in D\setminus{}A(B_r^+)\). Now delete the arc \(tl_2\) from \(B_t^+\) and add the arc \(l_1l_2\) instead. We have then obtained a \(B_t^+\) (arc disjoint from \(B_r^+\)) that is not an out-star, as desired. So we may now consider the case when \(|S_1| \leq 3\). Notice that \(|S_1|=1\) is impossible as \(\delta^-(D)\geq 2\), so we have \(|S_1| \geq 2\). However if \(|S_1|=2\), denoting \(S_2\) by \(\{t,y\}\), we have \(d_D^-(y)=1\), a contradiction. So we must have \(|S_1|=3\). Let \(S_1 = \{t,x,y\}\). As \(d_D^-(y), d_D^-(x) \geq 2\) we note that \(xy,yx,tx,ty \in A(D)\). As \(S_1\) is strong we note that \(xt \in A(D)\) or \(yt \in A(D)\) (or both). Without loss of generality assume that \(xt \in A(D)\). We now obtain the desired \(B_t^+\) and \(B_r^+\) as follows.

• If \(r=t\), then \(B_t^+ = \{tx,xy\}\) and \(B_r^+=\{ty,yx\}\).

• If \(r=x\), then \(B_t^+ = \{ty,yx\}\) and \(B_r^+=\{xt,xy\}\).

• If \(r=y\), then \(B_t^+ = \{tx,xy\}\) and \(B_r^+=\{yx,xt\}\).

Now, as \(B_t^+\) is not just an out-star it contains a vertex \(q\) which is neither the root or leaf. As \(D\) is a strong semicomplete digraph it contains a hamiltonian cycle, \(H=p_1 p_2 p_3 \ldots p_n p_1\). Without loss of generality assume that the cut-arc \(s t\) is the arc \(p_n p_1\). Then there must be exactly one arc in \(H\) leaving \(S_1\), say \(p_i p_{i+1}\). Note that \(p_1 p_2 \ldots p_i\) is a hamiltonian path in \(S_1\) and \(p_{i+1} p_{i+2} \ldots p_n\) is a hamiltonian path in \(D - V(S_1)\). Let \(Q\) be the union of \(B_t^+\) and the path \(p_{i+1} p_{i+2} \ldots p_n p_1\) where we add an arc from every leaf of \(B_{t}^+\) to \(p_{i+1}\) (which exists by the definition of the nice decomposition and the fact that \(t\) is not a leaf of \(B_{t}^+\)). Note that \(Q\) is a strong spanning subdigraph of \(D\).

Now construct \(B^+\) by starting with \(B_r^+\) and adding an arc from \(q\) (the vertex that was not the root or a leaf of \(B_{t}^+\)) to every vertex in \(V(D) \setminus V(S_1)\). Note that \(B^+\) is an out-branching in \(D\) rooted at \(r\) and \(D - A(B^+)\) contains all arcs of \(Q\) and is therefore strongly connected. This completes the proof of part (e) and therefore also of the theorem. ◻

As the digraph \(S_4\) has a non-separating out-branching \(B^+_v\) for each of its 4 vertices, the same holds for any digraph obtained from \(S_4\) by adding arcs parallel to existing ones. Thus we one can prove the following corollary of Theorem 16.

 ◻

Proof. Let \(D\) be a digraph with \(\alpha{}(D)=2 \leq \lambda{}(D)\) which consists of vertex disjoint strong semicomplete digraphs \(D_1, D_2\), such that there exists \(u_i \in V(D_i)\) that is not adjacent to any vertex in \(D_{3-i}\) for \(i=1,2\). As \(\delta^-(D) \geq 3\) we note that \(d_{D_i}^-(u_i) \geq 3\). Therefore \(|V(D_1)|,|V(D_2)| \geq 4\) and neither \(D_1\) nor \(D_2\) is isomorphic with \(W_1\) or \(W_2\) (see Figure 3). We will now construct in \(D\) an out-branching, \(B^+\), and a spanning strong subdigraph, \(Q\), which are arc-disjoint, as follows. To start this construction, consider the following three cases for \(i=1,2\).
Case 1. There are at least two vertices of in-degree one in \(D_i\).

As \(|V(D_i)| \geq 4\) and \(D_i\) is a strong semicomplete digraph, we note that there are exactly two vertices, \(r_1^i\) and \(r_2^i\), of in-degree one (there can be at most 3 vertices of in-degree one in a semicomplete digraph and if there were 3 such vertices in \(D_i\), then it would not be strong). By Theorem 18 and the fact that \(D_i\) is not isomorphic to \(W_2\), there exists an out-tree \(T_{r_i}^+\) rooted at \(r_1^i\) and spanning \(V(D_i)\setminus \{r_2^i\}\) such that \(D_i\setminus A(T_{r_i}^+)\) is strongly connected. Add the arcs of \(T_{r_i}^+\) to \(B^+\) and add the arcs of \(D_i\setminus A(T_{r_i}^+)\) to \(Q\). As \(\delta^-(D) \geq 3\) we note that there exists at least two \((D_{3-i},r_1^i)\)-arcs and at least two \((D_{3-i},r_2^i)\)-arcs in \(D\).
Case 2. There is exactly one vertex, \(r^i\), of in-degree one in \(D_i\).

As \(D_i\) is not isomorphic to \(W_1\), Theorem 18 implies that there is a non-separating out-branching, \(B_{r^i}^+\), in \(D_i\), rooted at \(r^i\). In this case add the arcs of \(B_{r^i}^+\) to \(B^+\) and the remaining arcs of \(D_i\) to \(Q\). As \(\delta^-(D) \geq 3\) we note that there exists at least two \((D_{3-i},r^i)\)-arcs in \(D\).
Case 3. \(\delta^-(D_i) \geq 2\).

As \(|V(D_i)| \geq 4\), then Theorem 18 (e) implies that \(D_i\) admits a nice decomposition \((S_1^i,S_2^i,\ldots,S_{p_i}^i)\), and for every \(r' \in S_1^i\) the digraph \(D_i\) contains a non-separating branching, rooted at \(r'\). As \(\lambda{}(D) \geq 2\), there must be a \((D_{3-i},S_1^i)\)-arc, \(ur^i\), in \(D\). Let \(B_{r^i}^+\) be a non-separating branching, rooted at \(r^i\) in \(D_i\). Add the arcs of \(B_{r^i}^+\) to \(B^+\) and the remaining arcs of \(D_i\) to \(Q\).
This completes our three cases. Note that \(Q\) contains a strong spanning subdigraph of \(D_1\) and of \(D_2\). Furthermore in cases 2 and 3, \(B^+\) contains an out-branching of \(D_i\) rooted at a vertex \(r^i\), such that there exists a \((D_{3-i},r^i)\)-arc in \(D\). In Case 1, \(B^+\) consists of an out-tree, rooted at \(r_1^i\), containing all vertices of \(D_i\) except \(r_2^i\), such that both \(r_1^i\) and \(r_2^i\) have at least two arcs into them from \(D_{3-i}\). We now consider the following possibilities.

We were in Case 2 or 3 for both \(D_1\) and \(D_2\). Add an arc from \(D_1\) to the root of the out-branching of \(D_2\) to \(B^+\). As \(\lambda{}(D) \geq 2\), we can add a further \((D_1,D_2)\)-arc and a \((D_2,D_1)\)-arc to \(Q\), in order for \(B^+\) and \(Q\) to fulfill the desired properties.

We were in Case 2 or 3 for \(D_1\) and Case 1 for \(D_2\). Add an arc from \(D_1\) to \(r_1^2\) and to \(r_2^2\). As there were at least two \((D_1,r_2^2)\)-arcs in \(D\) we can add a further \((D_1,r_2^2)\)-arc to \(Q\) and as \(\lambda{}(D) \geq 2\), we can add a \((D_2,D_1)\)-arc to \(Q\). Now \(B^+\) and \(Q\) fulfill the desired properties.

We were in Case 2 or 3 for \(D_2\) and Case 1 for \(D_1\). This case is analogous to the previous case.

We were in Case 1 for both \(D_1\) and \(D_2\). Add an arc from \(V(D_1) \setminus \{r_2^1\}\) to \(r_1^2\) and to \(r_2^2\) to \(B^+\) (which is possible as \(r_1^2\) and \(r_2^2\) have at least two arcs into them from \(D_1\)). Also add an arc from \(V(D_2) \setminus \{r_2^2\}\) to \(r_2^1\) to \(B^+\). Now \(B^+\) is an out-branching rooted at \(r_1^1\) in \(D\). As there are at least two arcs into \(r_1^i\) and into \(r_2^i\) from \(D_{3-i}\) we note that there are at least four \((D_2,D_1)\)-arcs and at least four \((D_1,D_2)\)-arcs in \(D\). We can therefore add a \((D_2,D_1)\)-arc and a \((D_1,D_2)\)-arc to \(Q\) such that \(Q\) and \(B^+\) are arc-disjoint. Now \(B^+\) and \(Q\) fulfill the desired properties, completing the proof of the theorem. ◻

Proof. Let \(D\) be a \(2\)-arc-strong digraph with \(\alpha(D) \leq 2\). By Theorem 18 we may assume that \(\alpha{}(D)=2\). By Lemma 1, we may assume that \(D\) has a strong spanning subdigraph \(H\) satisfying one of the conditions (B1)-(B3) in Case B of Corollary 1. Let \(D'=D\setminus A(H)\).

If \(D'\) has only one initial strong component, then, by Proposition 9 there is an out-branching in \(D'\) and the theorem is proved. So we may assume that \(R_1',R_2',\ldots,R_t'\) are the initial strong components in \(D'\) and \(t \geq 2\). For all \(i \in [t]\), let \(R_i = D \langle V(R_i') \rangle\). We will now prove the following claims.

Claim A:

\(t=2\) and \(|V(R_1)|,|V(R_2)| \geq 5\). Furthermore, all in-degrees in \(D'\) are at least two, except possibly for one vertex whose indegree is at least one. That is, there exists \(r \in V(D')\), such that \(d_{D'}^-(r) \geq 1\) and \(d_{D'}^-(x) \geq 2\) for all \(x \in V(D')\setminus \{r\}\).

In Case (i) we actually have \(\delta^-(D') \geq 3\).

Proof of Claim A: First consider Case (i) (when \(\delta^-(D) \geq 5\)). As \(\Delta^-(H)\leq 2\) we note that \(\delta^-(D')\geq 3\), and therefore also \(\delta_{D'}^-(R_1) \geq 3\). This further implies that \(|V(R_i)|=|V(R_i')| \geq 4\), since \(N_{D'}^-[x] \subseteq V(R_i')\), for all \(x\in V(R'_i)\) and \(i \in [t]\). Now noting that there is at most one vertex of \(H\) whose in-degree is more than 1, we see that \(R'_i\) contains a vertex with at least 4 in-neighbours inside \(R'_i\) so \(|V(R_i)|=|V(R_i')| \geq 5\) holds.

Now consider the Case (ii). In this case we note that all in-degrees in \(D'\) are at least two, except possibly for one vertex whose indegree is at least one. Let \(n_i=|V(R_i)|\) and note that the number of arcs in \(R_i\) is at least \(2n_i-1\) (as all arcs into a vertex in \(R_i\) belong to \(R_i\)). As \(D\) is oriented this implies that \({n_i \choose 2} \geq |E(V_i)| \geq 2n_i-1\). As \({n_i \choose 2} < 2n_i-1\) if \(n_i \in [4]\), we must have \(n_i \geq 5\), which implies that \(|V(R_i)| \geq 5\) in all cases.

For the sake of contradiction assume that \(t \geq 3\). Let \(x_1 \in V(R_1)\) be an arbitrary vertex with \(d^+_H(x_1)=d^-_H(x_1)=1\) and let \(N_1\) be the set of the two neighbours of \(x_1\) in \(H\). As \(|V(R_2)|\geq 5\) there are at least 3 vertices in \(V(R_2)\) that are not in \(N_1\). By part (B) in Corollary 1 we note that at most two vertices in \(H\) have degree more than two, so we can can choose a vertex \(x_2 \in V(R_2) \setminus N_1\) such that \(d^+_H(x_2)=d^-_H(x_2)=1\). Let \(N_2\) be the set of the two neighbours of \(x_2\) in \(H\). Now there exists a vertex \(x_3 \in V(R_3) \setminus (N_1 \cup N_2)\) which implies that \(\{x_1,x_2,x_3\}\) is an independent set in \(D\), contradicting \(\alpha(D) \leq 2\). Therefore \(t=2\), which completes the proof of Claim A.

Claim B:

\(R_1\) and \(R_2\) are semicomplete digraphs. Furthermore, for all \(z \in V(D)\) the following holds,

\[|N_H^+(z) \cap V(R_1)|,|N_H^+(z) \cap V(R_2)|,|N_H^-(z) \cap V(R_1)|,|N_H^-(z) \cap V(R_2)| \leq 1\]

Proof of Claim B: For the sake of contradiction assume that \(x_1,y_1 \in V(R_1)\) and \(x_1\) and \(y_1\) are non-adjacent in \(D\). Let \(N_2 = (N_H^+(x_1) \cup N_H^-(x_1) \cup N_H^+(y_1) \cup N_H^-(y_1)) \cap V(R_2)\). If \(V(R_2) \not\subseteq N_2\), then let \(z_2 \in V(R_2)\setminus N_2\) and note that \(\{x_1,y_1,z_2\}\) is independent in \(D\), contradicting that \(\alpha(D) \leq 2\). So, \(V(R_2) \subseteq N_2\), which implies that \(|N_2| \geq |V(R_2)| \geq 5\), by Claim A. By Corollary 1, we note that \(d_H(x_1)+d_H(y_1) \leq 6\), which implies the following,

\[6 \geq |N_H^+(x_1) \cap V(R_2)| + |N_H^-(x_1) \cap V(R_2)| + |N_H^+(y_1) \cap V(R_2)| + |N_H^-(y_1) \cap V(R_2)| \geq |N_2| \geq 5\]

First consider the case when \(|N_H^+(x_1) \cap V(R_2)| \geq 2\). By the construction of \(H\) we note that \(|N_H^+(x_1) \cap V(R_2)|=2\), so let \(N_H^+(x_1) \cap V(R_2)=\{x_2,y_2\}\). By Corollary 1, \(x_2\) and \(y_2\) are non-adjacent in \(D\). As \(\alpha(D)=2\) we note that either \(x_2\) or \(y_2\) has to be adjacent to \(y_1\). Without loss of generality assume that \(y_2\) is adjacent to \(y_1\). As \(y_2\) is adjacent to both \(x_1\) and \(y_1\) in \(D\) we note that we must have \(d_H(x_1)+d_H(y_1) = 6\), as \(H\) satisfies one of (B2), (B3) in Corollary 1 (and \(|N_2|=|V(R_2)|=5\)).

If \(|N_H^-(x_1) \cap V(R_2)| \geq 2\) or \(|N_H^+(y_1) \cap V(R_2)| \geq 2\) or \(|N_H^-(y_1) \cap V(R_2)| \geq 2\) then we analogously can show that \(d_H(x_1)+d_H(y_1) = 6\) and there exists two non-adjacent vertices \(x_2\) and \(y_2\) in \(R_2\).

If we had considered \(\{x_2,y_2\}\) instead of \(\{x_1,y_1\}\) then we would analogously have obtain \(d_H(x_2)+d_H(y_2) = 6\). However, by part (B) in Corollary 1 we note that it is not possible to have vertex-disjoint sets, \(\{x_1,y_1\}\) and \(\{x_2,y_2\}\), such that \(d_H(x_1)+d_H(y_1) = 6 = d_H(x_2)+d_H(y_2)\). Therefore \(R_1\) is semicomplete. Analogously we can show that \(R_2\) is also a semicomplete digraphs.

Let \(z \in V(D)\) be arbitrary. For the sake of contradiction assume that \(|N_H^+(z) \cap V(R_1)| \geq 2\). By Corollary 1 we must have \(|N_H^+(z) \cap V(R_1)| = 2\), so let \(N_H^+(z) \cap V(R_1) = \{x_1,y_1\}\). By Corollary 1 \(x_1\) and \(y_1\) are non-adjacent in \(D\). This contradicts the fact that \(R_1\) is semicomplete. Therefore \(|N_H^+(z) \cap V(R_1)| \leq 1\). Analogously \(|N_H^+(z) \cap R_2|,|N_H^-(z) \cap R_1|,|N_H^-(z) \cap R_2| \leq 1\), which completes the proof of Claim B.

Claim C:

Let \(y \in V(D) \setminus (V(R_1) \cup V(R_2))\) be arbitrary. If \(y\) has at most one arc entering it from \(V(R_1)\) in \(D\), then \(y\) is adjacent to all vertices in \(V(R_2)\) and furthermore has at least four arcs entering it from \(V(R_2)\).

Analogously, if \(y\) has at most one arc entering it from \(V(R_2)\) in \(D\), then \(y\) is adjacent to all vertices in \(V(R_1)\) and furthermore has at least four arcs entering it from \(V(R_1)\).

The above implies that every vertex in \(V(D) \setminus (V(R_1) \cup V(R_2))\) has at least four arcs entering it from \(V(R_1) \cup V(R_2)\) in \(D\).

Proof of Claim C: Assume that \(y \in V(D) \setminus (V(R_1) \cup V(R_2))\) and \(y\) has at most one arc entering it from \(V(R_1)\) in \(D\). For the sake of contradiction assume that there exists \(r_2 \in V(R_2)\) which is non-adjacent to \(y\) (in \(D\)). By Claim B, we note that \(|N_H^+(r_2) \cap V(R_1)|,|N_H^-(r_2) \cap V(R_1)|,|N_H^+(y) \cap V(R_1)|,|N_H^-(y) \cap V(R_1)| \leq 1\). As \(R_1'\) and \(R_2'\) are initial strong components in \(D'\), and therefore all arcs between \(r_2\) and \(R_1\) in \(D\) belong to \(H\), we note that \(r_2\) is adjacent to at most two vertices in \(R_1\) (in \(D\)). As \(y\) has at most one arc entering it from \(V(R_1)\) in \(D\) and at most one arc from \(y\) to \(R_1\) in \(H\) (and therefore also in \(D\), as \(R_1'\) is an initial strong components in \(D'\)), we note that \(y\) is adjacent to at most two vertices in \(R_1\) (in \(D\)). As \(|V(R_1)| \geq 5\), by Claim A, this implies that there exists a \(r_1 \in V(R_1)\) which is not adjacent to \(r_2\) or \(y\) in \(D\), contradicting \(\alpha(D)=2\). Therefore \(y\) is adjacent to every vertex in \(R_2\).

As \(R_2'\) was an initial strong component in \(D'\) and \(y \not\in V(R_2')\) we note that every arc from \(y\) to \(R_2\) in \(D\) belongs to \(H\). By Claim A and Claim B, we note that \(|N_H^+(y) \cap V(R_2)| \leq 1\) and \(|V(R_2)| \geq 5\), which implies that there are at least four arcs from \(V(R_2)\) to \(y\) in \(D\). This completes the first part of the proof of Claim C. The second part is proven analogously (by swapping the names of \(R_1\) and \(R_2\)).

Let \(x \in V(D) \setminus (V(R_1) \cup V(R_2))\) be arbitrary. If \(x\) has less than two arcs entering it from \(R_i\) then it has four arcs entering it from \(R_{3-i}\) (\(i \in [2]\)). And if \(x\) has at least two arcs entering it from both \(R_1\) and from \(R_2\), then it also has at least four arcs entering it from \(V(R_1) \cup V(R_2)\). This completes the proof of Claim C.

Construction of \(R_1^*\). Initially let \(R_1^*=R_1\). Now for every \(u \in V(D) \setminus (V(R_1^*) \cup V(R_2))\) with at least one arc into \(R_1^*\) in \(D\) and at most one arc from \(R_2\) to \(u\), add \(u\) to \(R_1^*\). Continue this process until no further vertex can be added.

Claim D: \(R_1^*\) is a strong semicomplete digraph.

Proof of Claim D: Let \(Q = V(R_1^*) \setminus V(R_1)\). That is, \(Q\) denotes the set of vertices added to \(R_1\) in the construction of \(R^*_1\). By construction, when it was added to the current \(R^*_1\) each such vertex had at least one arc into the current set \(V(R_1^*)\) and at most one arc entering it from \(V(R_2)\) in \(D\). We will first show that \(R_1^*\) is semicomplete. Assume for the sake of contradiction that \(q_1,q_2 \in V(R_1^*)\) are non-adjacent in \(D\). By Claim B we note that \(q_1\) and \(q_2\) cannot both belong to \(V(R_1)\). By part 2 of Claim C we note that we cannot have \(q_1 \in V(R_1)\) and \(q_2 \in Q\) (or vice versa), which implies that we must have \(q_1, q_2 \in Q\). This implies that \(q_1\) and \(q_2\) both have at most one arc into them from \(V(R_2)\). By Claim B, \(|N_H^+(q_1) \cap V(R_2)|,|N_H^+(q_2) \cap V(R_2)| \leq 1\), which implies that \(|N_D^+(q_1) \cap V(R_2)|,|N_D^+(q_2) \cap V(R_2)| \leq 1\). Therefore each of \(q_1\) and \(q_2\) are adjacent to at most two vertices in \(R_2\). As \(|V(R_2)| \geq 5\), there is a vertex \(r_2 \in V(R_2)\) which is non-adjacent to both \(q_1\) and \(q_2\) in \(D\), contradicting that \(\alpha(D) \leq 2\). Therefore \(R_1^*\) is semicomplete.

As \(R_1\) is strongly connected and every vertex we add in the process of building \(R_1^*\) has an arc into the current set \(R_1^*\) and an arc (actually at least 4 arcs) entering it from \(R_1\) (and \(R_1 \subseteq R_1^*\)), by Claim C, we note that the current set \(R_1^*\) is strongly connected in every step of the construction. Therefore the final \(R_1^*\) is also strongly connected. This completes the proof of Claim D.

Definitions. By Claim A and D and Proposition 14 we note that \(R_1^*\) has a nice decomposition \((S_1, \dots , S_p)\). If \(p \geq 2\) then there is only one arc entering \(S_1\) in \(R_1^*\) so let \(uv\) be an arc entering \(S_1\) in \(D\), which does not belong to \(R_1^*\). Such an arc exists as \(D\) is \(2\)-arc-strong. If \(p=1\) then \(R_1^*\) is \(2\)-arc-strong. In this case let \(uv\) be any arc entering \(R_1^*\) in \(D\). Let \(D^* = D' - uv\) (that is, delete the arc \(uv\) from \(D'\)).

Claim E:

There exists an out-branching \(B_1^+\) in \(R_1^*\) rooted at \(v\), such that \(R_1^* - A(B_1^+)\) is strongly connected.

Furthermore there exists an out-branching \(B_2^+\) in \(R_2\), such that \(R_2 - A(B_2^+)\) is strongly connected.

Proof of Claim E: As \(R_1^*\) is strongly connected by Claim D, We can apply Theorem 18 to \(R_1^*\). By Claim A we note that \(|V(R_1^*)| \geq 5\) and therefore \(R_1^*\) is not isomorphic to \(W_1\).

Also, by Claim A we note that all vertices of \(R_1\), except possibly one, have in-degree at least two in \(R_1\). As every vertex we add to \(R_1\) in the construction of \(R_1^*\) have in-degree at least four (from \(R_1\), by Claim C), we note that all vertices of \(R_1^*\), except possibly one, have in-degree at least two in \(R_1^*\). Therefore we are in case (c)-(e) of Theorem 18.

Note that if there is a vertex of in-degree one in \(R_1^*\), then \(v\) is that vertex. Furthermore \(v \in S_1\) (where \(S_1\) was defined just above Claim E, as part of the nice decomposition on \(R_1^*\)). Therefore by Theorem 18 we note that \(R_1^*\) contains a non-separating out-branching rooted at \(v\), which completes the first part of the proof of Claim E.

The second part of Claim E, follows analogously, by Theorem 18.

Completion of the proof. Let \(B^+= B_1^+ \cup B_2^+\) (defined in Claim E) and let \(Q = (R_1^* - A(B_1^+)) \cup (R_2 - A(B_2^+))\) and let \(V^* = V(R_1^*) \cup V(R_2)\). Note that \(B^+\) consists of two vertex-disjoint out-trees (whose union span \(V^*\)) and \(Q\) of two vertex-disjoint strong components (whose union also span \(V^*\)). Let \(P_{12}\) be a path from \(V(R_1^*)\) to \(V(R_2)\) in \(D^*\) and let \(P_{21}\) be a path from \(V(R_2)\) to \(V(R_1^*)\) in \(D^*\) Add the arcs of \(P_{12}\) and \(P_{21}\) to \(Q\). For every vertex \(p \in (V(P_{12}) \cup V(P_{21})) \setminus V^*\) do the following. Add an arc, which is not in \(A(P_{12}) \cup A(P_{21})\), from \(V(R_1^*) \cup V(R_2)\) to \(p\) to \(B^+\). This is possible by Claim C and the fact that there are at most two arcs in \(A(P_{12}) \cup A(P_{21})\) leaving \(V(R_1^*) \cup V(R_2)\) (at most one leaves \(V(R_1^*)\) and at most one leaves \(V(R_2)\)). Furthermore if \(p = u\) (recall that the arc \(uv\) was defined above Claim E), then make sure the added arc leaves \(V(R_2)\) (and not \(V(R_1^*)\)), which is possible as \(u\) was not added to \(R_1^*\) and therefore has at least two arcs into it from \(V(R_2)\) (here we used that the arc \(uv\) enters \(R^*_1\)). Finally add \(p\) to \(V^*\).

When this process is completed \(V^*=V(R^*_1)\cup V(R_2)\cup V(P_{12})\cup V(P_{21})\), \(Q\) induces a strong subgraph on the vertex set \(V^*\) and \(B^+\) still consist of two out-trees also spanning \(V^*\), one of which is rooted at \(v\). Furthermore the arc \(uv\) is not used above and if \(u \in V^*\) then it belongs to the out-tree not rooted at \(v\). We now add the remaining vertices as follows. While \(V^* \not= V(D)\) let \(P'\) be any \((V^*,V^*)\)-path in \(D^*\) with at least one internal vertex. We can construct \(P'\) by letting \(p_0p_1\) be any arc out of \(V^*\) in \(D^*\) and then taking any path from \(p_1\) back to \(V^*\) in \(D^*\). Now add \(A(P')\) to \(Q\) and for every vertex \(p \in V(P') \setminus V^*\) do the following (analogously to above). Add an arc, which is not in \(A(P')\), from \(V(R_1) \cup V(R_2)\) to \(p\) to \(B^+\), which is possible by Claim C and the fact that there is at most one arc in \(A(P')\) leaving \(V(R_1) \cup V(R_2)\). Furthermore if \(p = u\) (recall that the arc \(uv\) was defined above Claim E), then make sure the added arc leaves \(V(R_2)\) (and not \(V(R_1^*)\)), which is possible as \(u\) was not added to \(R_1^*\) and therefore has at least two arcs into it from \(V(R_2)\) (here we used that the arc \(uv\) enters \(R^*_1\)). Finally add \(p\) to \(V^*\).

We continue the above process until \(V^*=V(D)\). Now \(Q\) is a strong spanning subgraph of \(D\), which does not include any arcs from \(B^+\) and also does not include the arc \(uv\). \(B^+\) consists of two out-trees, one rooted at \(v\) and \(u\) belonging to the out-tree which was not rooted at \(v\). Therefore by adding the arc \(uv\) to \(B^+\) we obtain a spanning out-branching of \(D\) which is arc-disjoint to \(Q\), thereby completing the proof. ◻

Proof. Let \(D\) be a semicomplete digraph on at least five vertices. If \(D\) is strong, as \(D\) contains at least five vertices, then we find a spanning tree in the complement of a Hamiltonian cycle of \(D\). This spanning tree is clearly safe.

So, assume that \(D\) is not strong and denote by \(C_1, C_2, \dots ,C_t\) the strongly connected components of \(D\) such that there is no arc from \(C_i\) to \(C_j\) if \(i>j\). We denote by \(K\) the subdigraph of \(D\) containing the vertices \(V(D)\) and the set of arcs of \(D\) connecting its strong components (that is the arcs \(uv\) with \(u\in C_i\), \(v\in C_j\) and \(i\neq j\)). Moreover, for every \(i=1,\dots ,t\) let \(x_i\) be a vertex of \(C_i\) and \(P\) be the path \(x_1\dots x_t\). If there exists a spanning tree \(T\) of \(D\) all of whose arcs are in the subdigraph \(K'=K\setminus A(P)\), then \(T\) is a safe spanning tree of \(D\). Thus we have to check that \(K'\) is a connected subdigraph of \(D\).

First, if there exist \(i\) and \(j\) such that \(|C_i|\ge 2\) and \(|C_j|\ge 2\), then we pick a vertex \(y_i\) in \(C_i\) different from \(x_i\) and a vertex \(y_j\) in \(C_j\) different from \(x_j\). In \(K'\), every vertex not in \(C_i\) is adjacent to \(y_i\) and every vertex in \(C_i\) is adjacent to \(y_j\). So, \(K'\) is connected in this case.

Moreover, if \(t\ge 4\) then in \(K'\) every vertex of \(D\setminus C_1\cup C_2\) is adjacent to \(x_1\) and every vertex of \(D\setminus C_{t-1}\cup C_t\) is adjacent to \(x_t\). So, \(K'\) is connected.

Thus we may assume that \(t\le 3\) and that there exists \(i_0\in \{1,\dots ,t\}\) such that for every \(i\neq i_0\), the component \(C_i\) has size 1 exactly. If \(t=3\), then, as \(D\) contains at least 5 vertices, we have \(|V(C_{i_0})|\ge 3\). If \(i_0=1\), then \(K'\) contains all the arcs from \(V(C_1)-x_1\) to \(\{x_2,x_3\}\) and the arc \(x_1x_3\). So \(K'\) is connected. The case \(i_0=3\) is symmetrical.

So we may assume that \(i_0=2\). Let \(y_2 \in V(C_2) \setminus \{x_2\}\) be arbitrary and let \(K^* = K \setminus \{x_1x_2,y_2x_3\}\). As every vertex in \(V(C_2)\) is adjacent to \(x_1\) or \(x_3\) in \(K^*\) and \(x_1x_3 \in A(K^*)\) we note that \(K^*\) is a spanning connected subgraph of \(D\) and we can therefore in \(K^*\) find a safe spanning tree of \(D\).

Finally, if \(t=2\), by symmetry again we can assume that \(i_0=1\). We have \(|V(C_1)|\ge 4\) and so \(C_1\) contains an arc \(xy\) such that \(C_1\setminus xy\) is strongly connected. In this case the arcs from \(V(C_1)\setminus \{x\}\) to \(x_2\) plus the arc \(xy\) form the arcs of a safe spanning tree of \(D\). ◻

Proof. Let \(D\) and \(T\) as stated, and let \(C\) be a terminal strong component of \(D[V(T)]\setminus A(T)\).

Suppose first that \(V(D)\setminus V(T)=\{x\}\). As \(\lambda(D)\ge 2\), there are at least two arcs from \(C\) to \(x\). Let be \(u\) an in-neighbour of \(x\) in \(C\). The digraph \(D \setminus (A(T) \cup \{ux\})\) is still strong and so \(T+ux\) is a non-separating spanning tree of \(D\).

Now, assume that \(V(D)\setminus V(T)=\{x,y\}\). If there are two arcs \(ux\) and \(vx\) from \(C\) to \(x\), then \(T'=T+ux\) is a tree on \(n-1\) vertices such that \(D\setminus A(T')\) is strongly connected and we can conclude from the previous case that \(D\) admits a separating spanning tree. So, as \(\lambda(D)\ge 2\), there are at least two arcs from \(C\) to \(\{x,y\}\) and we can assume that one, say \(ux\), has head \(x\) and the other, say \(vy\), has head \(y\). Similarly, we can assume by the previous case, that if \(C'\) is an initial strong component of \(D[V(T)]\setminus A(T)\), then there exist two arcs \(xu'\) and \(yv'\) with \(u',v'\in C'\). As \(D[\{x,y\}]\) is semicomplete, we can assume without loss of generality that \(xy\) is an arc of \(D\). Now it is easy to check that \(D\setminus (A(T)\cup\{vy,xu'\})\) is strongly connected and that \(D\) admits the non-separating spanning tree \(T+vy+xu'\). ◻

Proof. If \(D\) is semicomplete, then the result follows from Lemma 2. So we may assume that \(\alpha{}(D)=2\). As the Ramsey number \(R(3,5)\) is 14 [15] and \(\alpha(D)=2\), it follows that if \(|V|\geq 14\), then \(D\) contains a semicomplete subdigraph on five vertices. Hence we may assume below that \(D_1\) is a semicomplete digraphs of \(D\) on 5 vertices. By Lemma 2, \(D_1\) contains a safe spanning tree. So let \(R\) be a maximal induced subdigraph of \(D\) containing \(V(D_1)\) and admitting a safe spanning tree. We now show that \(R=D\). Suppose for a contradiction that this is not the case.

Let \(T\) be a safe spanning tree of \(R\) and consider a vertex \(x\) of \(S=D[V\setminus V(R)]\). The vertex \(x\) has at most one in-neighbour in \(D_1\). Indeed, otherwise, assume that \(y\) and \(z\) are two in-neighbours of \(x\) in \(D_1\) with \(yz\) being an arc of \(D_1\) (recall that \(D_1\) is semicomplete). But then, \(T+yx\) would be a safe spanning tree of \(D[V(R)\cup x]\), a contradiction to the maximality of \(R\). Similarly, \(x\) has at most one out-neighbour in \(D_1\). So we can conclude that \(S\) is a semicomplete subdigraph of \(D\). Indeed, otherwise, \(S\) would contain an independent set \(\{u,v\}\) of size two. But as \(u\) and \(v\) have each at most two neighbours in \(D_1\), there would exist in \(D_1\) a vertex not adjacent to any of \(u\) or \(v\), contradicting \(\alpha(D)=2\).

First, assume that \(S\) contains a safe spanning tree \(T'\) and denote by \(C\) a strong terminal component of \(R\). As \(\lambda (D)\ge 2\), there exist at least two arcs \(xu\) and \(yv\) from \(C\) to \(S\) (with \(x,y\in C\) and \(u,v\in S\)). If \(u\neq v\), then there is an arc between \(u\) and \(v\) as \(S\) is semicomplete. Without loss of generality assume that \(uv\) is an arc of \(S\) and let \(e\) be the arc \(yv\). If \(u=v\) then we can choose arbitrarily \(e=xu\) or \(e=yv\). In both cases \(T+T'+e\) is a safe spanning tree of \(D\), contradicting the maximality of \(R\).

So, \(S\) has no safe spanning tree and as \(S\) is semicomplete, it follows from Lemma 2, that \(|V(S)|\le 4\). We also have \(|V(S)|>1\), as a unique vertex always has a safe spanning tree. Thus, to conclude the proof of the Lemma, we have three cases to handle: \(|V(S)|\in \{2,3,4\}\).

Assume first that \(S\) contains two vertices. Then, \(D \setminus A(T)\) is strong, \(D\setminus T\) has size two and is semicomplete. So, by Claim 1, \(D\) has a separating spanning tree, a contradiction again to the maximality of \(R\).

Now assume that \(S\) contains three vertices, and denote by \(C\) a strong terminal component of \(R\). As previously, as \(\lambda (D)\ge 2\), there exist at least two arcs \(xu\) and \(yv\) from \(C\) to \(S\) (with \(x,y\in C\) and \(u,v\in S\)). If \(u\neq v\), as \(S\) is semicomplete there is an arc between \(u\) and \(v\). Without loss of generality assume that \(uv\) is an arc of \(S\) and let \(e\) be the arc \(yv\). If \(u=v\) then we can choose arbitrarily \(e=xu\) or \(e=yv\). To conclude, denote \(T+e\) by \(T'\) and notice that \(D \setminus A(T')\) is strongly connected. As \(D\setminus T'\) has size two and is semicomplete, by Claim 1, \(D\) has a separating spanning tree, a contradiction again to the maximality of \(R\).

Finally, assume that \(S\) contains four vertices. As in the previous case, we can find an arc \(e=zw\) with \(z\in R\) and \(w\in S\) such that \(D \setminus (A(T) \cup \{e\})\) is strongly connected. As \(S\) as four vertices, \(w\) has in-degree or out-degree at least 2 in \(S\). Assume that \(w\) has out-degree at least 2 and denote by \(u\) and \(v\) two out-neighbours of \(w\) in \(S\) such that \(uv\) is an arc of \(D\). So, if we remove the arc \(wv\) from the digraph \(D \setminus (A(T) \cup \{e\})\), the resulting digraph still contains the path \(wuv\) from \(w\) to \(u\) and so is still strongly connected. That is, if we denote by \(T'\) the tree \(T+e+wv\), the digraph \(D \setminus A(T')\) is strongly connected and \(D - T'\) is semicomplete and has size two. Thus by Claim 1, \(D\) has a separating spanning tree, a contradiction again to the maximality of \(R\). The case when \(w\) has in-degree at least 2 in \(S\) is analogous. ◻

Proof. Note that \(H\) has 12 arcs and 6 vertices so if \(H\) would have a pair of arc-disjoint subdigraphs \(T,S\) where \(T\) is a spanning tree and \(S\) a strong spanning digraph, then \(|A(S)|\leq 7\) must hold. This implies that \(S\) is either a hamiltonian cycle of \(H\) or it consist of a cycle \(C\) and a \((C,C)\)-path \(P\) which picks up the remaining vertices of \(V\). Now note that the only cycle lengths of \(D\) are 3 and 6. We now use that \(H\) has a number of automorphisms: there are 4 pairs of 3-cycles joined by a hamiltonian cycle on their vertices, namely \((abca,xyzx)\), \((ayza,bcxb)\), \((abza, cxyc)\), \((ayca,bzxb)\). Hence up to automorphisms there is only one hamiltonian cycle, namely \(C_1=abcxyza\). It is easy to check that \(D \setminus A(C_1)\) is not connected. Hence, if \(T,S\) exist then we must have \(|A(S)|=7\) and \(S\) must consist of a 3-cycle \(C\) and a \((C,C)\)-path \(P\) which picks up the remaining 3 vertices of \(V\). By the symmetries above, we may assume that \(C=abca\). Again, by permuting the vertices \(a,b,c\) if necessary, we can assume that \(P\) starts with the arc \(cx\). This implies that \(P=cxyza\) (as \(P\) picks up all the vertices \(x,y,z\)). Now we see that \(S\) contains the hamiltonian cycle \(abcxyza\) and we saw above that removing the arcs of this cycle we disconnect the graph. ◻

Proof. As every vertex of \(\hat{D}\) has in- and out-degree 2 we see that if \(T,S\) is a pair of arc-disjoint spanning subdigraphs of \(\hat{D}\) such that \(T\) is connected and \(S\) is strongly connected, then \(T\) must be a hamiltonian path in \(\hat{D}\) (as \(d_S^+(x),d_S^-(x) \geq 1\) for every vertex \(x \in V(\hat{D})\) and therefore \(d_T^+(x),d_T^-(x) \leq 1\)). Let \(T=p_1p_2\ldots p_8\). Let \(C\) denote the arcs on the hamiltonian cycle, \(v_1v_2\ldots{}v_8v_1\) and let \(\bar{C} = A(\hat{D}) \setminus C\). We first prove the following statement.

(i)

\(p_i p_{i+1}, p_{i+1} p_{i+2} \in C\) is not possible for any \(i \in [6]\).

For the sake of contradiction, assume the above is true and without loss of generality that \(p_i = v_1\). That is, \(v_1 v_2 v_3\) is a subpath of \(T\). Continuing along \(T\) out of \(v_3\) and into \(v_1\) we note that all arcs of \(T\) belong to \(C\) (i.e. we cannot use the arc \(v_3 v_1\) in \(T\), so the only possible arc out of \(v_3\) is \(v_3 v_4\) and the only possible arc into \(v_1\) is \(v_8 v_1\), etc.). However \(S\) would then contain two disjoint \(4\)-cycles plus an extra arc, meaning it is not strongly connected, a contradiction.

As \(T\) is a hamiltonian path we note that \(p_i p_{i+1} \in C\) for some \(i \in \{2,3,4,5\}\) (otherwise \(T\) contains a \(4\)-cycle). By (i) we must have \(p_{i-1} p_{i}, p_{i+1} p_{i+2} \in \bar{C}\). Without loss of generality assume that \(p_{i}=v_4\), which implies that \(v_6 v_4 v_5 v_3\) is a subpath of \(T\). As \(T\) is a path (and \(i \leq 5\)) we must have that \(v_6 v_4 v_5 v_3 v_1\) is a subpath of \(T\) (as \(v_3 v_4 \not\in A(T)\)). This implies that the arcs \(v_2 v_3, v_3 v_4, v_4 v_2 \in A(S)\) (as \(d_S^+(v_3),d_S^-(v_3),d_S^+(v_4),d_S^-(v_4) \geq 1\)). As \(S\) has to contain arcs into and out of \(\{v_2,v_3,v_4\}\) we must have \(v_1v_2, v_2v_8 \in A(S)\). But now all arcs incident with \(v_2\) are in \(S\), a contradiction. ◻

Proof. Let \(C\) be a hamiltonian cycle of \(D\) and let \(X_1,X_2,\ldots{},X_k\) be the vertex sets of the connected components of \(H=UG(D)\setminus A(C)\). If \(k=1\) we are done, so assume that \(k\geq 2\). Note that each component has at least 3 vertices as \(d_H(v)\geq 2\), and \(D\) contains no 2-cycle.

Suppose first that \(k\geq 3\) and consider a vertex \(v\in X_i\) for some \(i\in [k]\). In \(UG(D)\) the vertex \(v\) has at most 2 neighbours outside \(X_i\). If \(v\) has no neighbours in some \(X_q\), \(q\neq i\), then let \(w\) be a non-neighbour of \(v\) in \(X_j\), \(j\not\in \{i,q\}\) and let \(z\) be an arbitrary non-neighbour of \(w\) in \(X_q\). Then \(\{v,w,z\}\) is an independent set, contradiction. Therefore \(k=3\) and every vertex in \(X_i\) has a neighbour in each of the other sets \(X_j\), implying that we can pick \(x_i\in X_i\), \(i\in [3]\) such that \(\{x_1,x_2,x_3\}\) is an independent set, contradiction.

Hence \(k=2\) and we may assume that \(|X_1|\geq |X_2|\). As \(|V|\geq 9\) this implies that \(|X_1|\geq 5\) and hence, as every arc between \(X_1\) and \(X_2\) belongs to \(C\) this implies that \(X_2\) induces a complete subgraph of \(UG(D)\) (every vertex of \(X_1\) must be adjacent at least one of the vertices \(x,y\) in a pair of non-adjacent vertices \(x,y\in X_2\) so if such a pair existed, at least one of \(x,y\) would be incident to 3 arcs of \(C\), contradiction). Hence, by Theorem 19, we can assume that \(|X_2|\leq 4\) and that \(D[X_1]\) is not semicomplete. Note that for every pair of vertices \(u,v\in X_1\) such that \(D\) has no arc between these, every vertex of \(X_2\) has at least one edge to \(\{u,v\}\) in \(A(C)\). Also note that \(\delta^0(D[X_i])\geq 1\), \(i\in [2]\) as only the arcs of \(C\) go between \(X_1\) and \(X_2\).

First suppose that \(|X_2|=4\). If \(X_1\) contains vertices \(u_1,u_2,v_1,v_2\) all distinct except possibly \(u_2=v_1\) so that there is no arc in \(D\) between \(u_i\) and \(v_i\) for \(i=1,2\), then we get the contradiction that the undirected graph induced by \(A(C)\) contains either a 4-cycle or an 8-cycle, contradicting the \(C\) is a hamiltonian cycle of \(D\). Thus \(X_1\) contains exactly one pair \(u,v\) of non-adjacent vertices and, by Theorem 19, we may assume that \(|X_1|=5\) so \(D\) has 9 vertices. As all 4 vertices of \(X_2\) are adjacent to either \(u\) or \(v\), exactly two of them are adjacent to \(u\) and the other two are adjacent to \(v\). Now it is easy to see that \(C\) has at most one arc inside \(X_2\) (otherwise \(C\) would contain a 3-cycle or a 6-cycle as a subdigraph). Consider first the case when \(C\) uses no arc inside \(X_2\). Then we can label the vertices of \(V\) such that \(X_1=\{v_1,v_2,v_4,v_6,v_8\}\), \(X_2=\{v_3,v_5,v_7,v_9\}\) and \(C=v_1v_2\ldots{}v_9v_1\).

Suppose first that \(D\) contains the arc \(v_3v_5\). Then let \(wv_4\) be an arbitrary arc entering \(v_4\) in \(D[X_1]\) (this exists as \(\delta^0(D[X_1])\geq 1\)) and let \(T'\) be a spanning tree avoiding the arcs \(wv_4,v_1v_2\) in \(G'=UG(D[X_1])\). This tree exists as \(G'\setminus \{wv_4,v_1v_2\}\) has 5 vertices and 7 edges and hence is connected. Then we obtain a strong spanning subdigraph \(S\) of \(D\) from \(C\) by deleting the arc \(v_3v_4\) and adding the arcs \(v_3v_5,wv_4\) and note that \(S\) is arc-disjoint from the spanning tree formed by \(T'\) and the edges of the path \(v_4v_3v_9v_7v_5\) in \(UG(D)\), see Figure 8 (a).

Hence we can assume that \(v_5v_3\in A(D)\) and by an analogous argument we can assume that \(v_7v_5,v_9v_7\in A(D)\). Now let \(v_2w\) be an arbitrary arc leaving \(v_2\) in \(D[V(X_1)]\), let \(T''\) be a spanning tree avoiding the arcs \(v_1v_2,v_2w\) in \(G'\) and let \(S'\) be the strong spanning subdigraph of \(D\) obtained from \(C\) by deleting the arc \(v_2v_3\) and adding the arcs of the directed path \(v_9v_7v_5v_3\) and the arc \(v_2w\) and note that \(S'\) is arc-disjoint from the spanning tree formed by \(T''\) and the edges of the path \(v_5v_9v_3v_7\) (in \(UG(D)\)) and the arc \(v_2v_3\). See Figure 8 (b).

Next we consider the case when \(C\) contains one arc of \(D[V(X_2)]\). In this case, we may assume that \(v_5\) and \(v_8\) are the two vertices in \(X_1\) that are non-adjacent in \(D\) and \(X_2=\{x_4,x_6,x_7,x_9\}\) such that \(x_4 x_5 x_6\) and \(x_7 x_8 x_9\) are subpaths of \(C\). We may furthermore assume without loss of generality that \(x_6 x_7 \in A(C)\) (the case when \(x_9 x_4 \in A(C)\) is identical, by renaming vertices). This implies that we can label \(C\) as \(C=v_1v_2\ldots{}v_9v_1\), and \(X_1=\{v_1,v_2,v_3,v_5,v_8\}\) and \(X_2=\{v_4,v_6,v_7,v_9\}\) (and \(v_5\) and \(v_8\) are non-adjacent in \(D\)).

If \(v_7v_9\) is an arc of \(D[V(X_2)]\), then let \(j \in [3]\) be chosen such that \(v_j\) is an out-neighbour of \(v_8\) in \(D[V(X_1)]\) and let \(j' \in [3]\setminus \{j\}\) be arbitrary. Now the strong spanning subdigraph \(S\) consisting of the cycle \(v_1v_2\ldots{}v_7v_9v_1\) and the path \(v_7v_8v_j\) is arc-disjoint from the spanning tree using the edges \(v_4v_6,v_4v_7,v_4v_9,v_9v_8,v_8v_{j'},v_5v_1,v_5v_2,v_5v_3\). Hence we can assume that \(v_9v_7\) is an arc of \(D[V(X_2)]\). A similar argument shows that we may assume that \(v_6v_4\) is an arc of \(D[V(X_2)]\). Now using that \(\delta^0(D)\geq 2\) this implies that the remaining arcs in \(D[V(X_2)]\) are \(v_7v_4,v_9v_6\) and \(v_4v_9\). See Figure 9 (a).

Now choose \(p \in [3]\) such that \(v_pv_5\) is an arc of \(D[V(X_1)]\) and let \(S'\) be the strong spanning subdigraph of \(D\) formed by the arcs of the cycle \(v_1v_2v_3v_4v_9v_1\) and the path \(v_pv_5v_6v_7v_8v_9\). Let \(q \in [3] \setminus \{p\}\) be arbitrary and note that \(D \setminus A(S')\) is connected as it contains the spanning tree on the edges \(v_4v_5, v_4v_6,v_6v_9,v_7v_9,v_8v_1,v_8v_2,v_8v_3,v_5v_q\), see Figure 9 (b). This completes the case when \(|X_2|=4\).

Consider now the case when \(|X_2|=3\). Recall that \(X_2\) induces a 3-cycle in \(UG(D)\). Let \(G\) be the complement of \(UG[X_1]\). That is, \(V(G)=V(X_1)\) and \(uv \in E(G)\) if and only if \(u\) and \(v\) are non-adjacent in \(D\). By Theorem 19 we may assume that \(\alpha(G) \leq 4\) and as \(\alpha(D)=2\) we may assume that \(G\) contains no \(3\)-cycle. As \(|V(G)| \geq 6\) we note that we must therefore have a matching of size two in \(G\). Let \(uv\) and \(u'v'\) be two edges in a matching in \(G\).

Note that at least three arcs between \(X_2\) and \(\{u,v\}\) belong to \(C\) (as otherwise there would be an independent set of size 3 containing \(u\) and \(v\)). There are also at least three arcs between \(X_2\) and \(\{u',v'\}\) in \(C\). As \(|X_2|=3\) these 6 arcs are all the arcs between \(X_2\) and \(X_1\). Without loss of generality assume that \(u\) is incident to two arcs between \(X_1\) and \(X_2\) and \(u'\) is also incident to two arcs between \(X_1\) and \(X_2\), which implies that both \(v\) and \(v'\) are incident with exactly one arc between \(X_1\) and \(X_2\). As \(\alpha(D)=2\) and \(\alpha(G)\leq 4\) we now note that \(|X_2|=6\) and \(E(G)=\{uv,u'v'\}\) or \(E(G)=\{uv,u'v',uu'\}\).

Let \(u_8=u\), \(u_4=v\), \(u_6=u'\) and \(u_1=v'\). We can now without loss of generality, label the vertices of \(V\) by \(u_1,\ldots{},u_9\) such that \(X_1=\{u_1,u_2,u_3,u_4,u_6,u_8\}\), \(X_2=\{u_5,u_7,u_9\}\), \(C=u_1u_2\ldots{}u_9u_1\) and there is no arc between \(u_1\) and \(u_6\) and no arc between \(u_4\) and \(u_8\). There may or may not be an arc between \(u_6\) and \(u_8\). See Figure 10.

Moreover, as \(\delta^+(D)\ge 2\) and \(D\) is oriented, we know that \(D[X_2]\) is a directed 3-cycle. If \(D\) contains the arc \(u_7u_9\), then as above we can find the desired pair \(S,T\), see Figure 11 (a).

Otherwise, it means that \(D[X_2]\) is the directed 3-cycle \(u_9u_7u_5u_9\), and then, as above we can find the desired pair \(S,T\), see Figure 11 (b).

 ◻

Proof. It is easy to check that \(v_0\) has two arc-disjoint paths to every other vertex and that every vertex different from \(v_0\) has two arc-disjoint paths to \(v_0\). This implies that \(T_r\) is 2-arc-strong. For the sake of contradiction assume that there is a hamiltonian path, \(P\), in \(T_r\), and that \(v_0\) can reach \(v_r\) in \(S = T_r \setminus A(P)\). As for every \(i\in [r-1]\) the two arcs \(u_iu_{i+1},v_iv_{i+1}\) form a 2-arc-cut of \(T_r\) seperating \(v_0\) from \(v_r\), one of these arcs must belong to \(S\) and the other to \(P\). Similarly, as for every \(i\in [r-2]\) the two arcs \(u_iu_{i+1},v_{i+1}v_{i+2}\) form a 2-arc-cut of \(T_r\) seperating \(v_0\) from \(v_r\) one of these arcs must belong to \(S\) and the other to \(P\). Let \(A_1 = \{u_1u_2, u_2u_3, \ldots, u_{r-1} u_r\}\) and let \(A_2 = \{v_1v_2, v_2v_3, \ldots, v_{r-1} v_r\}\), and note that by the previous argument we must have \(A_i \subseteq A(S)\) and \(A_{3-i} \subseteq A(P)\) for some \(i \in [2]\). Without loss of generality assume that \(A_1 \subseteq A(S)\) and \(A_2 \subseteq A(P)\), which implies that \(P\) cannot contain both \(u_2\) and \(u_3\), a contradiction to the existence of \(P\) and \(S\). ◻

Proof. For each \(r\geq 4\) let \(T_r\) be the 2-arc-strong tournament defined in Lemma 3 and form the digraph \(D_r\) from two copies \(T^1_r,T^2_r\) of \(T_r\) (whose vertices are superscripted) by adding two arbitrary arcs from \(V(T^i_r)\) to \(v^{3-i}_0\) for \(i=1,2\). Since each \(T_r\) is a tournament, we have \(\alpha{}(D_r)=2\). Moreover, as \(T^1_r\) and \(T^2_r\) arc 2-arc strong, \(D_r\) is 2-arc strongly connected also. Suppose that \(D_r\) has a hamiltonian path \(P\) such that \(D \setminus A(P)\) is strong. Without loss of generality \(P\) starts in \(V(T^1_r)\) and thus the restriction of \(P\) to \(V(T^2_r)\) is a hamiltonian path \(P'\) starting at \(v^2_0\). By Lemma 3 we note that \(v^2_0\) cannot reach \(v^2_r\) in \(T^2_r \setminus A(P')\), which implies that no vertex in \(T^1_r\) can reach \(v^2_r\) in \(D_r \setminus A(P)\). So \(D_r \setminus A(P)\) is not strong, a contradiction. ◻

Proof. Let \(G\) be a 2-edge connected graph with \(\delta(G)\ge 4\) and \(\alpha(G) \le 2\). It is easy to see that every connected graph with independence number at least 2 has a spanning tree with a number of leaves at most its independence number. Hence \(G\) contains a Hamiltonian path \(P\). If AY\(G \setminus E(P)\) is connected, we are done. Otherwise let \(X_1,X_2,\dots ,X_p\) be the connected components of \(G \setminus E(P)\). Notice that as \(\delta(G)\ge 4\) and \(P\) is a path, we have \(\delta(G \setminus E(P))\ge 2\), and in particular, we have \(|X_i|\ge 3\) for all \(i=1,\dots ,p\). If \(p\ge 3\), consider \(u\) an extremity of \(P\) and assume without loss of generality that \(u\in X_1\) and that its neighbour \(v\) in \(P\) is in \(X_1\cup X_2\). It means that all the vertices of \(X_2\setminus \{v\}\) and \(X_3\) are non neighbours of \(u\) and hence must form a complete subgraph of \(G\). In particular, all the edges between \(X_2\setminus \{v\}\) and \(X_3\) are edges of \(P\), which is not possible as \(|X_2\setminus \{v\}|\ge 2\) and \(|X_3|\ge 3\), implying that \(P\) would contain a cycle. So, \(G \setminus E(P)\) contains exactly the two connected components \(X_1\) and \(X_2\).

Notice that the case \(|X_1|=|X_2|=3\) is not possible, as in this case, as \(\delta(G)\ge 4\), every vertex of \(X_1\) would have at least two neighbours in \(X_2\) and every vertex of \(X_2\) would have at least two neighbours in \(X_1\), and so \(P\) would contain a cycle, which is not possible. Hence \(\max\{|X_1|,|X_2|\}\geq 4\) and we may assume that \(|X_1|\geq 4\).

Assume first that \(\alpha(G[X_1])=\alpha(G[X_2])=1\), that is, they are both complete graphs. In this case, we will show how to build a Hamiltonian path and a spanning tree of \(G\) which are edge-disjoint. If \(x\) is a vertex of any complete graph \(K\) on at least 4 vertices, it is easy to find a Hamiltonian path which starts in \(x\) and a spanning tree which are edge-disjoint. Suppose first that \(|X_2|\ge 4\). Then it follows from the fact that \(G\) is 2-edge connected, that there exist two distinct edges \(x_1x_2\) and \(y_1y_2\) with \(x_1,y_1\in X_1\) and \(x_2,y_2\in X_2\). Now consider for \(i=1,2\) a Hamiltonian path \(P_i\) of \(G[X_i]\) starting in \(x_i\) and a spanning tree \(T_i\) of \(G[X_i]\) edge-disjoint from \(P_i\). We conclude by considering the Hamiltonian path \((P_1\cup P_2)+ x_1x_2\) of \(G\) edge-disjoint from the spanning tree \((T_1\cup T_2)+ y_1y_2\) of \(G\). Hence we may assume that \(|X_2|=3\) and denote the vertices in \(X_2\) by \(\{x_2,y_2,z_2\}\). As \(\delta(G)\ge 4\), there exist three distinct edges of \(G\) \(x_2x_1,y_2y_1,z_2z_1\) such that \(x_1\), \(y_1\) and \(z_1\) belong to \(X_1\). So, we consider a Hamiltonian path \(P_1\) of \(G[X_1]\) starting in \(x_1\) and a spanning tree \(T_1\) of \(G[X_1]\) edge-disjoint from \(P_1\). We conclude then with the Hamiltonian path \(P'=(P_1 \cup x_2y_2z_2)+x_2x_1\) of \(G\) and the spanning tree \(T_1 +x_2z_2+y_2y_1+z_2z_1\) of \(G\) edge-disjoint from \(P\).
If \(\alpha(G[X_1])=1\) and \(\alpha(G[X_2])=2\), then as \(\delta(G) \geq 4\), we must have \(|X_2| \geq 4\). In this case we may swap the names of \(X_1\) and \(X_2\), which implies that we may assume without loss of generality that \(\alpha(G[X_1])=2\). Let \(x_1\) and \(y_1\) be two vertices of \(X_1\) which are not adjacent in \(G\). As every vertex of \(X_2\) is adjacent to \(x_1\) or \(y_1\) in \(G\) and as the corresponding edges must be edges of \(P\), we have \(|X_2|\le 4\). Suppose \(|X_2|=4\). Then we will prove that \(G[X_1]\) is almost complete, that is it contains all the possible edges except \(x_1y_1\). Denote the vertices of \(X_2\) by \(\{x_2,y_2,z_2,t_2\}\), and as \(\alpha(G)=2\), we can assume that \(x_2\) and \(y_2\) are adjacent to \(x_1\) and that \(z_2\) and \(t_2\) are adjacent to \(y_1\). Assume first that \(G[X_1]\) contains two non-adjacent vertices \(z_1\) and \(t_1\) both distinct from \(x_1\) and \(y_1\). As \(\alpha(G)=2\), the vertex \(x_2\) has to be adjacent to \(z_1\) or \(t_1\). We can assume that \(z_1x_2\) is an edge of \(G\), but then \(y_2\) has to be adjacent to \(t_1\) as there is no cycle induced by the edges of \(P\). Similarly, we can assume that \(z_1z_2\) is an edge of \(P\), but then \(t_2\) cannot be adjacent to any of \(z_1,t_1\) without creating a cycle induced by the edges of \(P\). So, \(\{z_1,t_1,t_2\}\) is an independent set, contradicting \(\alpha(G)=2\). Now assume that \(X_1\) contains a vertex \(z_1\neq y_1\) which is non-adjacent to \(x_1\). Then \(z_2\) has to be adjacent to \(x_1\) or \(z_1\) and as \(x_2\) and \(y_2\) are already adjacent to \(x_1\) in \(P\), \(z_2\) must be adjacent to \(z_1\). Similarly, \(t_2\) is adjacent to \(z_1\), but then \(z_1z_2y_1t_2\) would form a cycle with the edges of \(P\), a contradiction. Similarly we can prove that every vertex of \(X_1\) except \(x_1\) is adjacent to \(y_1\) so \(G[X_1]\) is the graph \(K_{|X_1|}-x_1y_1\). As \(|X_1|\ge 4\), it is easy to find then in \(G[X_1]\) two vertex-disjoint paths \(P_1\) and \(P'_1\) such that \(V(P_1)\cup V(P'_1)=X_1\), the path \(P_1\) ends in \(x_1\) and the path \(P'_1\) ends in \(y_1\) and \(G[X_1]-P_1-P_2\) is connected and so contains a spanning tree \(T_1\). On the other hand, as \(\delta(G[X_2]-P)\ge 2\), the graph \(G[X_2]\) contains a 4-cycle. One of the edges of this 4-cycle goes from \(\{x_2,y_2\}\) to \(\{z_2,t_2\}\). So, denote this 4-cycle by \(abcda\) such that \(a\) is adjacent to \(x_1\) and \(d\) is adjacent to \(y_1\). Now, we consider the Hamiltonian path \(P'=(P_1\cup P'_1)+ab+bc+cd\) of \(G\). As \(b\) and \(c\) have at least one neighbour each in \(X_1\), we know that \(G \setminus E(P')\) has at most 2 connected components, one containing \(X_1\cup \{b,c\}\), the other one containing \(\{a,d\}\). But as \(\delta(G)\ge 4\), \(a\) has a neighbour in \(X_1\cup \{b,c\}\) different from \(x_1\), and so, \(G \setminus E(P')\) is connected.
The only remaining case is when \(|X_2|=3\). Denote the vertices of \(X_2\) by \(\{x_2,y_2,z_2\}\) and assume without loss of generality that \(x_2\) and \(y_2\) are adjacent to \(x_1\) and that \(z_2\) is adjacent to \(y_1\). As \(z_2\) as degree at least 4 in \(G\), there exist a vertex \(z_1\in X_1\) distinct from \(x_1\) and \(y_1\) such that \(z_1\) is a neighbour of \(z_2\) in \(P\). More generally, as \(\delta(G)\ge 4\), every vertex of \(X_2\) has exactly two neighbours in \(X_1\), which are then neighbours in \(P\), \(G[X_2]\) is a complete graph and finally every vertex of \(X_2\) has degree exactly 4. In particular, \(\{x_1,z_2\}\) is an independent set of size 2, and every vertex of \(X_1\setminus \{x_1,y_1,z_1\}\) is adjacent to \(x_1\). Now, let us focus on the extremities of the path \(P\). Both cannot lie in \(Y=\{x_1,y_1,z_1,x_2,y_2,z_2\}\) as the only vertices of \(Y\) with degree less than 2 in \(P\) are \(y_1\) and \(z_1\), and they cannot be both extremities of \(P\) as otherwise, \(P\) would be the path \(y_1z_2z_1\). So, denote by \(p\) an extremity of \(P\) not lying in \(Y\) and recall that \(x_1\) is adjacent to every vertex of \(V\setminus Y\) so \(x_1p\) is an edge of \(G\). Now consider the Hamiltonian path \(P'\) of \(G\) defined by \(P'=(P-x_2x_1-x_1y_2)+x_2y_2+x_1p\). To conclude, let us prove that \(G \setminus E(P')\) is connected. Indeed, every vertex of \(V\setminus \{y_1,z_1,z_2\}\) is linked to \(x_1\), and all the corresponding edges except \(px_1\) are edges of \(G \setminus E(P')\). So, \(G \setminus E(P')\) induces a connected graph on \(Z=V\setminus \{y_1,z_1,z_2,p\}\). Moreover, \(z_2\) is adjacent to \(x_2\) and \(x_2z_2\) is not an edge of \(P'\). And by choice, \(p\) is not adjacent to \(z_2\) and so has a neighbour in \(Z\) different from \(x_1\). Finally, \(y_1\) and \(z_1\) have both at least one neighbour in \(G \setminus E(P')\) which belongs to \(V\setminus \{y_1,z_1\}\). Thus, \(G \setminus E(P')\) is connected and the proof is complete. ◻