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