Graph theory: Prove that every closed trail (circuit) contains a cycle. **\- Background information:** I am studying graph theory in discrete mathematics. I have come across this question, but I need help with reasoning and understanding my professor's proof. **\- Original question and professor solution:**  to the end (green). 1. Where is "vj+1" coming from? 2. Why is the "v0, v1, ..., vi, vj+1, ..., vk" closed trail smaller than T(original trail)? Are we excluding few vertices? 3. By the argument, is it referring to "vi = vj" and "v0, v1, ..., vi, vj+1, ..., vk"? How can repeating this lead to a cycle in T?

Let me see if I can draw it.

The first part that you understand is this. Obviously it's a cycle.


0-1-2
| |
5-4-3


If this is not the case, the path must be coming back to itself at some point:


0--1-x-7--8
| / \ |
| 5-4-3 9
| |
12--11---10


where x is both i=2 and j=6. So we can skip over the loop by going from i=2 (x) to j+1=7. Because we are skipping over the loop, this outer cycle is obviously shorter than T.

I think it should be clear that repeating this procedure will skip over all loops.