Length of a circuit

Question

I am reading an article about "Longest Paths in Digraphs". In the proof there is a step that they considered as a trivial step, it seems easy but I am not being able to write or concieve an exact proof for it.

We have a strong digraph $D$, that has minimum in degree $h$ and minimum out degree $k$. Let $C$ be the longest circuit in $D$ of length $c$; then $c\ge \max(h,k)+1$.

Why is that true?

I think it is solved by contradiction and we can find a larger circuit.

Suppose to contradiction that $c< \max(h,k)+1$ and suppose without loss of generality that $\max(h,k)=k$, then $c \le k$ which means that every vertex on the circuit has at least $1$ out neighbor outside $C$.

But how can we continue to find a larger circuit?

Answer 1

I will use @Mike idea in his answer, but write a much shorter version of the answer.

Let $P=v_p\cdots v_1$ be the longest path in $D$, (starting from $v_p$ to $v_1$). All the out neighbors of $v_1$ are on $P$, since otherwise we get a longer path. $d^+(v_1)\ge k$, let $c$ be the maximum integer such that $(v_1,v_c)\in E(D)$ then we have a circuit $C=v_cv_{c-1}\cdots v_1$ of length greater than or equal to $k+1$.

Answer 2

Let us assume here that $k \ge h$ as you did and let $P$ be a path of length $c \ge \max(h,k)+1 = k+1$. Your line of reasoning shows that there is indeed such a path $P$. We use this to show how to get a circuit $C$ with at least $k+1$ vertices as follows:

Now let us write (*) $P=y_1y_2\ldots y_c$ where $y_1$ is the first vertex in $P$ and where $y_c$ is the last vertex in $P$.

1. If $y$ has a neighbor $y'=y_{c+1}$ outside of $P$ then add the arc $y_cy' =y_cy_{c+1}$ to $P$, now $P$'s length is $c+1$ instead of $c$ as it was before.

2. If all of $y$'s neighbours are in $P$, then let $j$ be the smallest integer such that $y_cy_j$ is an arc in $G$, where $y_j$ is as in (*). Then $j \le c-k$ [why is this] so $C= y_jy_{j+1} \ldots y_cy_j$ is a circuit of length at least $k+1$.

Now note that 1. can be true for at most $n-k$ times as the number of vertices in any path $P'$ in $G$ is of course upper-bounded by the number of vertices in the digraph $G$. So you will indeed obtain a circuit of length at least $k+1$ after adding at most $n-k-1$ vertices to $P$ as in 1. above.

I trust that you can handle the case where $h > k$.