(related to Theorem: Characterization of Semi-Eulerian Graphs)

- Assume, a simple graph \(G(V,E)\) is semi-Eulerian.
- Then there is an semi-Eulerian tour between a starting and finishing vertices \(v\) and \(w\).
- Adding an edge \(e\) between \(v\) and \(w\) creates an Eulerian tour, and thus an Eulerian graph \(G'(V,E')\) with \(E':=E\cup\{e\}\).
- By the characterization of Eulerian graphs, \(G'\) is connected, and each of its vertices has an even degree.
- Whenever this trail passes through a vertex, there is a contribution of \(2\) to the degree of that vertex.
- By removing the edge \(e\) again, we see that \(v\) and \(w\) are exactly the two vertices with an odd degree.
- Removing the edge \(e\) does not disconnect the graph \(G'\), because there is still an open trail between \(v\) and \(w\).
- Thus, also \(G\) is connected.

- Assume, \(G\) is a connected graph with exactly two vertices with an odd degree, \(v\) and \(w\).
- Add an edge \(e\) between \(v\) and \(w\) to create an Eulerian tour, and thus an Eulerian graph \(G'(V,E')\) with \(E':=E\cup\{e\}\).
- By the characterization of Eulerian graphs, \(G'\) is connected, and each of its vertices has an even degree.
- Removal of the edge \(e\) from this trail produces an open trail, i.e. a trail that includes every edge of \(G\) but is not a closed trail.
- So, \(G\) is semi-Eulerian.∎

**Aldous Joan M., Wilson Robin J.**: "Graphs and Applications - An Introductory Approach", Springer, 2000