Graphs: Prove that this graph is Semi-Eulerian

767 Views Asked by At

Prove that a graph is Semi-Eulerian if and only if it has 2 vertices with odd degrees. Any hints how to start the proof?

2

There are 2 best solutions below

0
On

The graph also needs to be connected. Start by finding a path between the two vertices with odd degree.

0
On

Hint You probably covered the theorem about Eulerian graphs before.

If you did, add an extra edge between the vertices of odd degree, find an Eulerian circuit, make it end at the extra edge and delete.