1

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

Community
  • 1
John Kanti
  • 47

1 Answers1

1

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.

Ebearr
  • 866
  • 1
    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 ?

     – John Kanti Jun 24 '15 at 03:34
  • 1
    @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. – Ebearr Jun 24 '15 at 03:39
  • 1
    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 [(http://i.stack.imgur.com/aB6cH.jpg)]

     – Tandee Holwa Jun 24 '15 at 03:55
  • @JohnKanti They are integers between $1$ and $l$. We just don't know exactly which vertices in $P$ are neighbors of $v_0$. It would depend on the particular graph. But we are showing this is true for any graph. So the indices are variable. – Ebearr Jun 24 '15 at 03:57
  • 1
    @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$. – Ebearr Jun 24 '15 at 03:59
  • 1
    why ? it is exactly like the problem – Tandee Holwa Jun 24 '15 at 04:02
  • I think @TandeeHolwa is right, this picture is what I am talking about, – John Kanti Jun 24 '15 at 04:03
  • 1
    @TandeeHolwa How is it exactly like the problem? $P= v_0 v_1 \cdots v_l$. What is vertex $w$? You have just labeled the vertices differently then how we set up the problem. – Ebearr Jun 24 '15 at 04:05
  • @TandeeHolwa To make your picture like the problem, label your vertices as $v_1$ instead of $x$, $v_2$ instead of $w$, $v_3$ instead of $u$, $v_4$ instead of $z$, and $v_5$ instead of $y$. – Ebearr Jun 24 '15 at 04:08