Clarification on Eulirian cycle proof

27 Views Asked by At

enter image description here

I have trouble in understanding this proof can some one clarify the following elements: (1)Why does it follow that if T has maximum length, then $v_0=v_k$?(2)What does E represent?(3)What does E(T) mean?

Thank you!

1

There are 1 best solutions below

1
On BEST ANSWER

$(1)$ By hypothesis, the degree of every vertex is even. So if you can enter a vertex, you must be able to leave it along a different edge, thus extending the trail $T$. There is one exception to this, the starting vertex. Since you leave $v_0$ at the start of the trail, once the remaining $\text{deg }v_0-2$ edges have been used in the trail, $T$ must end upon entering $v_0$ a final time (i.e. the would be edge along which you could exit the vertex is the one which began the trail.

$(2)$ $E$ gives the set of edges in a graph

$(3)$ $E(T)$ denotes the edges of the trail $T$.