Euler Graphs and Hamiltonian Graphs

EULER TRAIL: A trail in G is said to be an Euler Trail if it includes all the edges of graph G. Thus a trail is Euler if each edge of G is in the trail exactly once.

  • PDF / 319,725 Bytes
  • 10 Pages / 439.37 x 666.142 pts Page_size
  • 58 Downloads / 345 Views

DOWNLOAD

REPORT


Euler Graphs and Hamiltonian Graphs

3.1 Euler Tour and Euler Graph Euler trail: A trail in G is said to be an Euler Trail if it includes all the edges of graph G. Thus a trail is Euler if each edge of G is in the trail exactly once. Tour: A tour of G is a closed walk of G which includes every edge of G at least once. Euler tour: An Euler Tour of a graph G is a tour which includes every edge of G exactly once. In other words, a closed Euler Trail is an Euler Tour. Euler graph: A graph G is called Eulerian or Euler graph if it has an Euler Tour. For example, the graphs G1 and G2 of Fig. 3.1 have an Euler trail and an Euler tour, respectively. In G1 , an Euler trail is given by the sequence of edges e1 ; e2 ; e3 ; e4 ; e5 ; e6 ; e7 ; e8 ; e9 ; e10 ; while in G2 an Euler tour is given by e1 ; e2 ; e3 ; e4 ; e5 ; e6 ; e7 ; e8 ; e9 ; e10 ; e11 ; e12 :

Fig. 3.1 G1 is not an Euler graph, but G2 is an Euler graph

In G1 : it has an Euler trail but not Euler tour because it is not closed. In G2 : all the vertices are even degree. Hence, it is Eulerian which implies it contains the Euler tour. Since G2 contains Euler Tour so it is Eulerian.

S. Saha Ray, Graph Theory with Algorithms and its Applications, DOI: 10.1007/978-81-322-0750-4_3, Ó Springer India 2013

25

26

3 Euler Graphs and Hamiltonian Graphs

Theorem 3.1(Euler Theorem) A connected graph G is Eulerian (Euler graph) iff every vertex has an even degree. Proof Necessary condition: Let the graph G be Eulerian.  Let W : u ! u be an Euler tour and v be any internal vertex such that v 6¼ u. Suppose, v appears k times in this Euler tour W: Since every time an edge arrives at v, another edge departs from v, and therefore, dG ðvÞ ¼ 2k (Even). Also, dG ðuÞ is 2, since W starts and ends at u. Hence, the graph G has vertices of all even degree. Sufficient condition: Let us assume G is a non-trivial connected graph such that for all vertex v 2 VðGÞ; dG ðvÞ is even. To show: G is Eulerian.  Let W ¼ e1 . . .en : v0 ! vn ; where ei ¼ vi1 vi and W be the largest trail in G. It follows that all e ¼ vn w 2 EðGÞ are among the edges of W; otherwise We would be the longer than W in G, which is a contradiction. In particular, v0 ¼ vn ;i.e., the trail W is a closed trail. Indeed if v0 6¼ vn then vn may appear k times in the trail W; then dðvn Þ ¼ 2ðk  1Þ þ 1 ¼ 2k  1 (Odd), which is a contradiction. So W should be closed trail. If W is not an Euler tour, then since G is connected, there exists an edge f ¼ vi u 2 EðGÞ for some i; such that f is not inW: Then, eiþ1 . . .. . .en e1 . . .ei f is a trail in G and it is longer than W: This contradiction to the choice of W proves the claim. So, W is a closed Euler tour. Hence G is a Euler graph. h Theorem 3.2 A connected graph has an Euler trail iff it has at most two vertices of odd degree. Proof Necessary condition:  Let the graph G has an Euler trail u ! v. Let w be any vertex which is different from u and v, i.e., w 6¼ u; v. If w is a vertex different from the origin and terminus of the trail, the degree of w is even. Since if w occ

Data Loading...