Baltic Way 2019

We proceed by induction on $n$, the number of vertices.

For the base case we consider $n=4$ where the only possible digraph is the complete digraph which contains $2$ disjoint cycles of length $2$.

We now assume that any $3$-out digraph, with $n-1\ge 4$ vertices, contains $2$ disjoint cycles.

Let $G$ be a digraph on $n$ vertices failing our assumption.

Then $G$ has no bidirectional edges. If $uw$ is a bidirectional edge then $G\setminus \{u,w\}$ is still $1$-out so it contains a cycle, which paired with the $2$-cycle made by the bidirectional edge $uw$ gives the desired disjoint cycles.

The main idea allowing us to prove the result is using edge contractions. If there is an edge $uv$ such that $u,v$ have no common parent, we can modify $G$ to a new digraph $G^{\prime }$ by removing $u$ and $v$ and adding a vertex $w$ for which its outgoing edges come to all children of $v$ and its ingoing edges come from all parents of $u$ and $v$. $G^{\prime }$ has $n-1$ nodes and is still $3$-out, as $u,v$ had no common parent, so by the inductive assumption $G^{\prime }$ contains $2$ disjoint cycles. If $w$ is not in any of the cycles they were contained in $G$ and we are done. The other option is that $w$ is contained in one of the cycles, this implies the other cycle is in $G$. We distinguish the cases when the cycle in-edge of $w$ comes from $u$'s in-edge or from $v$'s in-edge. Replacing $w$ in the first case by $uv$ and in the second by $v$ we get the other cycle in $G$ and we are done.

The only remaining option is when every edge of $G$ has a «witness» (defined as common parent to both its end-vertices). Let $v$ be a vertex having the smallest in-degree (we denote in-degree as $d^{-}$). As there are $3n$ edges in total we have $d^{-}(v)\le 3$.

Case 1: $d^{-}(v)=0$. Then the edge starting in $v$ has no witnesses.

Case 2: $d^{-}(v)=1$. Then the edge ending in $v$ has no witnesses.

Case 3: $d^{-}(v)=2$. Let $u,w$ be two parents of $v$. Then $u$ has to be the witness to $wv$ and $w$ to $uv$ implying $uw$ is a bidirectional edge which is a contradiction.

Case 4: $d^{-}(v)=3$. Since our graph is exactly $3$-out and the minimal in-degree is $3$, then all the vertices have in-degree $3$. Given a vertex $x$ and its parents $u,v,w$ we show that $u,v,w$ make a $3$-cycle. Indeed, we notice that each of the witnesses of $ux,vx,wx$ must be among $u,v,w$ implying that the $u,v,w$ induced subgraph is $1$-in. This combined with the fact bidirectional edges do not exist, we conclude that $u,v,w$ make a $3$-cycle as claimed. If we reverse the edges of $G$ we notice that all the above arguments still apply, as $G$ is both exactly $3$-out and exactly $3$-in, so children of $x$ also form a $3$-cycle. As there are no bidirectional edges, the children and parents of $x$ are disjoint and give $2$ disjoint $3$-cycles.