0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Well for each vertex when we goes into it we have to go out of it as well except for the starting vertex, which we go out first but we still need to go into it at last. So each vertex consists of (in, out) pairs and since edge cannot be reused the degree of vertices must be even. $\endgroup$
    – cr001
    Nov 25, 2015 at 7:59
  • $\begingroup$ @cr001 , you are right. $\endgroup$
    – Mithlesh Upadhyay
    Nov 25, 2015 at 8:03

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for very nice explanation. $\endgroup$
    – Mithlesh Upadhyay
    Nov 25, 2015 at 8:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .