1
$\begingroup$

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$

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

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$:

    example

    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$.

$\endgroup$
  • 1
    $\begingroup$ 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$ $\endgroup$ – John Kanti Jun 23 '15 at 10:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Rebecca J. Stones Jun 23 '15 at 11:04
  • 1
    $\begingroup$ 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$ ? $\endgroup$ – John Kanti Jun 23 '15 at 13:21
  • 1
    $\begingroup$ 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 ? $\endgroup$ – John Kanti Jun 23 '15 at 14:48
  • 1
    $\begingroup$ @Rebecca J. Stones , why you assume cycle size $\geq n-(n-k)+1$ could you please give me some explanation ? $\endgroup$ – John Kanti Jun 23 '15 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.