In: Advanced Math
A graph is G is semi-Eulerian if there are distinct vertices u,
v ∈ V (G), u =v such
that there is a trail from u to v which goes over every edge of G.
The following
sequence of questions is towards a proof of the following:
Theorem 1. A connected graph G is semi-Eulerian
(but not Eulerian) if and only
if it has exactly two vertices of odd degree.
Let G be semi-Eulerian with a trail t starting at a vertex
u0 and ending at a vertex
v0 Let G 0 be a graph obtained by adding an
edge e0 joining u0 and v0 , so
that
G 0 − e = G.
(a) Prove that given a semi-Eulerian trail t in G from
v0 to u0 , it is possible to
construct a Eulerian trail in G0.
(b) Prove that given an Eulerian trail in G 0 it is possible to
construct a semi-Eulerian
trail in G.
(c) Prove Theorem 1.
a) Let be
a semi-Eulerian trail in G from v0 to u0.
Now, let us add the edge e in G. Then, we can see that this edges
makes this trail in a Eulerian trail. Hence, we get a Eulerian
trail in G0
b) Now, let us take an Eulerian trail in G0. Then we
will write the trail as ,
since it passes each edge once (basically I reset the starting
parameter of the trail such that it starts from v_0 and it
traverses the edges e at the veyr end). Then, if we take out the
edge e from the graph G0 . Then, we can get a semi
Eulerian trail in the graph in G.
c) From part a) and b) we get that a Graph can be converted from Semi Eulerian graph to a Eulerian graph by adding an edge between the endpoints of the semi Eulerian trail. And we can remove an edge from Eulerian graph to make it semi Eulerian. Now, we also know that a Graph is Eulerian if and only if every vertex has even degree. Then, from these information we get that a graph is Semi Eulerian if and only if it has exactly two odd degree vertices. This can be concluded because we are only removing one edge from a Eulerian graph to make it semi Eulerian.