1
$\begingroup$

Suppose the following situation: this is found at (Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$)

Let $P=v_0v_1 \dots v_l$ be a longest path in $G$. $v_0$ has to have additional neighbors by the degree constraint. All of the neighbors of $v_0$ have to be in $P$, otherwise $P$ could be extended. Therefore $v_0$ has at least $k$ neighbors in $P$. Let $j$ be the maximum index of a neighbor of $v_0$. By the previous statement we have that $j \ge k$. Thus we have the cycle $v_0v_1 \dots v_jv_0$, which has length at least $k+1$.

After many interpretation I did not understand what he meant by $j$ is the maximum index of a neighbor. I assumed it to be directed graph ? In addition I could not understand why $j\geq k$ and why has length at least k+1. I tried but I could not. ?

$\endgroup$
1
$\begingroup$

We know that $v_0$ has at least $k$ neighbors in $P$. Now these neighbors have indices drawn from $\{1, \dots, l\}$ by definition. So by maximum index, he means let $j$ be the index such that $v_j$ is a neighbor of $v_0$ and $v_i$ is not a neighbor of $v_0$ for all $i > j$.

Now $j \ge k$ since if not, then $v_0$ does not have $k$ neighbors in $P$ which is a contradiction. You should be able to figure out the length argument from here.

Also, often times in graph theory, graphs are assumed to be undirected unless stated otherwise.

$\endgroup$
  • 1
    $\begingroup$ if $v_0$ is connected with $v_x$ and also with $v_y$ what is the rule to choose a maximum index is it $x$ or $y$ ? there must be some rules to classify $j$ as maximum index ? what is the idea of choosing indexes here ? $\endgroup$ – John Kanti Jun 24 '15 at 3:34
  • 1
    $\begingroup$ @JohnKanti I'm not sure I follow. Do you mean assume that $v_0$ has neighbors $v_x$ and $v_y$, how do you know what the maximum index is? Well that depends on $x$ and $y$. If $x > y$ then $x$ is the maximum index. If $y > x$, the $y$ is the maximum index. $\endgroup$ – Ebearr Jun 24 '15 at 3:39
  • 1
    $\begingroup$ as I understand you numbered every node, because both of $x$ and $y$ is the label of the node, they are not numbers see please this picture [(i.stack.imgur.com/aB6cH.jpg)] $\endgroup$ – Tandee Holwa Jun 24 '15 at 3:55
  • 1
    $\begingroup$ @TandeeHolwa The vertices in this problem are not like what is in your picture. The vertices in $P$ are $v_0, v_1, \dots, v_l$. $\endgroup$ – Ebearr Jun 24 '15 at 3:59
  • 1
    $\begingroup$ why ? it is exactly like the problem $\endgroup$ – Tandee Holwa Jun 24 '15 at 4:02

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.