24
$\begingroup$

Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$.

How would I show this? I understand that a cycle is a sequence of non-repeated vertices and the degree of a graph is the number of neighbors the vertex has.

$\endgroup$

3 Answers 3

33
$\begingroup$

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. Also, from the degree constraint $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$.

$\endgroup$
5
  • $\begingroup$ I think it is not formal proof, because you did not explain why $j \ge k$, when $ j = k $ $\endgroup$ Jun 20, 2015 at 23:42
  • $\begingroup$ what do you mean by maximum index... ? $\endgroup$ Jun 24, 2015 at 3:02
  • 4
    $\begingroup$ @TandeeHolwa The index of an element $x_j \in \{x_1, \dots, x_n \}$ is the subscript $j$. It is a formal proof: $j = k \Rightarrow j \geq k$ $\endgroup$ Aug 30, 2015 at 8:01
  • $\begingroup$ @PatrickStevens what do you mean by previous statement ? why is j>=k ? $\endgroup$
    – hemi
    Jun 1, 2018 at 10:17
  • $\begingroup$ @hemi There are at least $k$ distinct neighbours among the $v_1, \dots, v_j$. Therefore $j \geq k$, otherwise the neighbours couldn't fit in. $\endgroup$ Jun 1, 2018 at 22:29
2
$\begingroup$

This can be solved via the well-ordering principle. Let path P be the longest path in graph G that starts at point A, which has the lowest degree of the graph. If A has degree higher than 2, then it will have some neighboring point W. If W was not on P, then A would have a neighbor that's not on P, and then P would not be the longest path, so unless A's other neighbor is on the path as well, this creates a contradiction. As a result, W has to be on P, otherwise we'd have the said contradiction, meaning that all of A's neighbors are on P. This creates a cycle, and since a cycle has length of at least |V(G)| + 1, this path will have length of at least k + 1.

If there is an error with this, I just learned this in class about a week ago, so I'm far from perfect.

$\endgroup$
1
  • 2
    $\begingroup$ +1 for the answer, but the initial condition of A having minimum degree is incorrect. It is incorrect because with that condition I cannot make all the neighbor's on the path P. $\endgroup$ Jul 30, 2016 at 6:29
2
$\begingroup$

This proof uses the Pigeon Hole Principle. Also we assume k>=2.

Let's say our graph has n points a1, a2,...,an. Choose any point, WLOG say we choose a1. For simplicity call it b(1). Now a1 has k neighbors, so choose any one call it b2. Go from b1 to b2.

b1---b2

Now randomly choose a neighbor of b2 and call it b3. Go from b2 to b3.

b1---b2---b3

Note that we can continue this process till b(k+1).

b1---b2---b3.......---b(k+1)

Reason: This follows from Pigeon Hole Principle, Say we have reached up to b(i) for now where i<=k.

b1---b2---....---b(i)

Then before b(i), {b1,b2.....b(i-1)} we have i-1 terms that's <= k-1. We know that b(i) has k neighbors, therefore there exists a vertex (from PHP) that does not belong to our path and is a neighbor of b(i), so include it in the path as b(i+1). Therefore we can always have the above path.

Till now we have:

b1---b2.....---b(k+1)

Now, there are few cases:

(1) If b(k+1) is a neighbor of a1 then we can simply complete the cycle, it will have length k+1 and we are done.

(2) Else if a1 isn't a neighbor of b(k+1). Consider the set {b2,b3.....,b(k)} this has k-1 elements, and b(k+1) has k neighbors therefore by PHP, there exists an element not in this set and is a neighbor of b(k+1), call it b(k+2) and include it in our path.

b1---b2---.....b(k+1)---b(k+2)

Now if b(k+2) is a neighbor of b1 or b2, complete the cycle, we will have cycle of length k+2 or k+1 and we will be done. The set {b3,.....,b(k+1)} has k-1 elements, so if b1 and b2 are not neighbors of b(k+2) then again by PHP we can find a neighbor of its that is not in {b1,....,b(k+1)} call it b(k+3) and include it in our path.

Continue this test..

However this possibility of finding neighbor has to end sometime since we only have finitely many vertices. So there exists an i>=1 so that:

b(k+i) has a neighbor in {b1,b2,.....,b(i)}, if not then we can always find a neighbor of b(k+i) and go on..

Since {b(i+1),b(i+2).....b(k+i-1} has k-1 vertices, so if none of b1,b2,....,b(i) are neighbors of b(k+i) by PHP we can find a new vertex that's a neighbor of b(k+i).

So it's clear that process must terminate.

Therefor after finding such an i, complete the cycle by choosing suitable vertex from {b1,b2,...,b(i)} say it is j<=i. We get the cycle:

b(j)---b(j+1)---.......---b(k+i)---b(j)

Clearly it has length >= k+1 as j<=i. We are done.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .