# If $G$ is simple directed graph with $deg^+(v)\geq k \geq 1 \space \forall \space v \in V$ there is a simple cycle of at least size $k+1$

I have the following proof but it is tough could someone help me to understand it,

Proof: Start at an arbitrary node $v$ and mark it, and so on until you have marked all nodes in the series then a node $j$ is approached such that all its out edges connect it to marked nodes, choose one edge which points to the node with the minimum number of edges, and now node $j$ has at least $k$ out-edges, then the node with the lowest number in the path must be at least $k$ edges, together with node $j$ this edge closes of at least length $k+1$

• your proof is not clear, please give more details, – Tandee Holwa Jun 22 '15 at 21:04
• please provide with more explanation such that what you mean by '...one edge that point to the node with the minimum number of edges,..' – Tandee Holwa Jun 23 '15 at 0:17

It seems easiest to begin with the longest directed path, $(v_1,v_2,\ldots,v_n)$ say.

Then

• If $v_n$ has an out-neighbor $u \not\in \{v_1,v_2,\ldots,v_{n-1}\}$ then $(v_1,v_2,\ldots,v_n,u)$ is a longer directed path, giving a contradiction. So $v_n$ has at least $k$ distinct out-neighbors in $\{v_1,v_2,\ldots,v_{n-1}\}$.

• If $v_i$ is an out-neighbor of $v_n$, then $(v_i,v_{i+1},\ldots,v_n)$ is a directed cycle.

Here's an illustration where $n=7$:

Here we find $(v_2,v_3,\ldots,v_7)$ is a cycle.

• Since $v_n$ has at least $k$ distinct out-neighbors in $\{v_1,v_2,\ldots,v_{n-1}\}$, there is an out-neighbor $v_i$ of $v_n$ with $i \leqslant n-k$. Hence the longest such cycle has size $\geqslant n-(n-k)+1=k+1$.

• Thanks @Rebecca J. Stones, but I have question why $i\leq n-k$ ? and you said that 'The longest such cycle has size $k+1$' , I think this is the minimum cycle size, not the longest size. Is not it ? last but not least : $(v_i,v_{i+1},\ldots,v_n)$ is is not cycle becuse there are not vertex after node $v_n$ – John Kanti Jun 23 '15 at 10:00
• We have $i \leqslant n-k$ because there are $k$ vertices in $\{1,2,\ldots,n-1\}$ which are out-neighbors of $v_n$. We choose $i$ to be the smallest index of the out-neighbors. E.g. if the out-neighbors happen to be precisely $\{n-1,n-2,\ldots,n-k\}$, we choose $i=n-k$; in other cases $i<n-k$ (I drew the illustration to help with this). We're trying to maximize the cycle length here ("at least size $k-1$") so we don't want a minimum. With regards to the notation, I could write $v_i$ again at the end of $(v_i,v_{i+1},\ldots,v_n)$, but it doesn't really matter. – Rebecca J. Stones Jun 23 '15 at 11:04
• Thank you @Rebecca J. Stones for your explanation: Suppose we have $n=5$ nodes as $v_1v_2v_3v_4v_5$ and $v_5$ has $k=4$, so as you assume that $i\leqslant n-k \Rightarrow i\leqslant1$ does it make sense that we have $v_i$ with $i\leqslant1$ ? – John Kanti Jun 23 '15 at 13:21
• and the Theorem states that there is a simple cycle of at least size k+1, but you came up with something different "... longest such cycle has size $\geq n−(n−k)+1=k+1$" , which fact is true ? – John Kanti Jun 23 '15 at 14:48
• @Rebecca J. Stones , why you assume cycle size $\geq n-(n-k)+1$ could you please give me some explanation ? – John Kanti Jun 23 '15 at 16:36