BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Wednesday , June 28 2017
Home / Discrete mathematics / An undirected graph possess an Eulerian path if and only if, is connected and has either zero or two vertices of odd degree.

An undirected graph possess an Eulerian path if and only if, is connected and has either zero or two vertices of odd degree.

Proof: Suppose that the graph possess an eulerian path. That the graph must be connected is obvious. When the eulerian path is traced, we observe that every time the path meets a vertex, it goes through two edges which are incident with the vertex and have not been traced before. Thus, except for the two vertices at the two ends paths, the degree of any vertex in the graph must be ever. If the two vertices at the two ends of the eulerian path are distinct. If the coincide, all vertices have even

degree and the eulerian path becomes an eulerian circuit. Then the necessity of the stated condition is proved.

To prove the sufficiency of the stated condition,

we construct an eulerian path by starting at one of the two vertices that are of odd degree and going through the edges of the graph in such a way that no edge will be traced more than once. For a vertex of even degree, whenever the path “enters” the vertex through an edge, it can always “leave” the vertex through another edge that has not been traced before. Therefore, when the contraction eventually comes to an end, we must have reached the other vertex of odd degree. If all the edges in the graph were traced this way, clearly, we should have an eulerian path. If not all of the edges in the graph were traced we shall remove those edges that have been traced and obtain a sub graph formed by the remaining edges. The degrees of the vertices of this sub graph are all even. Moreover this sub graph must touch the path that we have traced at one or more vertices since the original graph is connected. Starting one of these vertices, we can again construct a path that passes through the edges. Because the degrees of the vertices are all even, this path must return eventually to the vertex at which it starts.
We can combine this path with the path we have constructed to obtain one which starts and ends at the two vertices of odd degree.

If necessary, the argument is repeated until we obtain a path that traverse all the edges in the graph.

Check Also

Procedure for computing shortest distance| Discrete Mathematics

Solution: The procedure for computing the shortest distance/path from a to any vertex G. Initially, ...

Leave a Reply

Your email address will not be published. Required fields are marked *