Graph Theory Cycle Graph Proof $G$ is a graph with $n \geq 3$ vertices and $\delta(G) \geq n/2$. I have already proven in $(a)$ that for each $k<n$, if G contains a copy of $C_k$, then G contains a copy of $P_k$. And in $(b)$, for each k, if G contains a copy of $P_k$, then G contains either a copy of $P_{k+1}$ or a copy of $C_{k+1}$.
I need to use $(a)$ and $(b)$ to prove that G contains a copy of $C_n$. I think that $\delta(G) \geq n/2$ implies that G contains a copy of $P_1$. I don't know how to use $(a)$ and $(b)$ to prove that it must follow that G contains a copy of $P_2$. I know by repeatedly doing this same step using induction I can prove that G must contain a copies all the way up to $P_n$, but I don't know how to finally conclude there is a copy of $C_n$. Can I have some help please showing me how to do this question ?
 A: You are correct about what you've done so far:

*

*For a path of length $1$, you don't even need the full power of $\delta(G) \ge \frac n2$: you just need to know that your graph has at least one edge.

*If we have a path of length $k$, then by (b) we can either extend it to a path of length $k+1$ or complete it to a cycle of length $k+1$. By (a), provided $k+1<n$, the cycle of length $k+1$ gives us a path of length $k+1$, too. So by induction, we can keep extending our path until (a) stops working...

...and now all you have to realize is that the only way (a) can stop working is if we have a cycle of length $n$, which is what we wanted!
Another possibly helpful thought for your intuition: if we end up with a path of length $n-1$, then it looks like (b) gives us two alternatives of either a path of length $n$ or a cycle of length $n$. However, there is no such thing as a path of length $n$ in our graph: it only has $n$ vertices, so $n-1$ is the longest path possible. So if we reach a length-$(n-1)$ path, then (b) will give us a length-$n$ cycle, at which point we are done!

(I am deliberately avoiding using the notation $P_k$, $C_k$, because graph theorists can't agree on whether $P_k$ has $k$ vertices or $k$ edges, and the difference is actually rather important in this proof.)
