Graph theory: Prove that every closed trail (circuit) contains a cycle.

Question

- 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:

- My questions:

I don't understand from the beginning (green) 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?

Answer 1

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.