◀ ▲ ▶Branches / Graph-theory / Proof

Proof

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

"\(\Rightarrow\)"

• 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.

"\(\Leftarrow\)"

• 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.
  ∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

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