What is connection of degrees of a connected undirected simple graph with Euler graph ? Why it should be all even degree vertices ? yes , I read here "every connected graph of all whose vertices have even degree contain no bridges." . It makes sense, Euler graph should not contain bridges. I found here induction proof. I know that is necessary condition,but I need another formal proof . Can you explain please.
Prove that an Eulerian graph is one in which all vertices have even degree?
Best Answer
By "Eulerian graph", I take it you mean a graph that has an Euler circuit, that is, a walk that uses each edge exactly once and returns to the vertex where it started.
What if your graph has a vertex of odd degree? If the walk starts there, once you leave the vertex, there are an even number of edges left to use. In order to use all the edges, when you return to the vertex where you started, you must also leave it. So if you start the walk at the vertex of odd degree, you can't end there.
If there's a vertex of odd degree and you don't start there, by a similar argument, you have to end there in order to use all the edges. So if you end there, you couldn't have started there.
For the other direction of the proof, when you start with a connected graph of all even degrees, there's an algorithm to find an Euler circuit. See http://www.graph-magics.com/articles/euler.php for instance.