Any Eulerian trail which is not an Eulerian circuit must start and end at an odd vertex.

621 Views Asked by At

Theorem Any Eulerian trail which is not an Eulerian circuit must start and end at an odd vertex.

https://proofwiki.org/wiki/Characteristics_of_Traversable_Graph

Proof:

Let G be a graph.

Suppose all the vertices are even, that is, there are no odd vertices.

Then G is Eulerian, and the result holds.

Similarly, by the same result, if G is Eulerian, it is by definition traversable.

So the question of graphs all of whose vertices are even is settled.

Sufficient Condition Suppose G is a connected graph for which exactly two vertices u,v are odd.

Let G′ be the graph formed by adding the edge uv.

Note that if there is already an edge uv in G, that will mean there is now more than one edge uv in G′.

Thus G′ will then be a multigraph or loop-multigraph, and uv a multiple edge.

Then G′ will have all its vertices even, and thus by the above result be Eulerian and by definition traversable.

Such an Eulerian circuit that traverses G′ can be written, for example, P′=(v,w,x,…,t,u,v).

Let us then remove the final edge uv from P′ to get the path P=(v,w,x,…,t,u).

It follows that the path P=(v,w,x,…,t,u) is a path in G which includes all edges in G.

Hence P traverses G and so G is traversable.

We note that u and v are the odd vertices of G.

Necessary Condition Suppose a graph G is traversable.

Then it has a Eulerian trail P.

If P is a circuit, then G is Eulerian and therefore has all even vertices.

Now, suppose P=(v,w,x,…,t,u) is not a circuit.

Let G′ be the graph formed by adding the edge uv.

Then the path P′=(v,w,x,…,t,u,v) is an Eulerian circuit and so G is Eulerian.

Hence all the vertices of G′ are even.

So the degrees of vertices u and v in G (and no other) are odd.

Again, we note that u and v are the odd vertices of G.

Hence the result.

I think this proof lacks a base case, an inductive hypothesis, and inductive step, so it is incomplete. I think the author adds edge $uv$ and removes the edge $uv$ as part of an attempt to do induction. Have I listed all the errors of the proof correctly?