What is Hamilton Circuit?
A Hamiltonian circuit in a graph G is a closed circuit or part of graph (may be complete graph as well) that visits every vertex in G exactly once. That means to complete a visit over the circuit no vertex will be visited multiple time. The below image is an example of Hamilton circuit.
A path which is followed to visit Hamilton Circuit is called Hamilton Path. That means a Hamilton Path visiting all vertices. The green path in the below image is a Hamilton Path.
What is Euler Circuit?
A Euler circuit in a graph G is a closed circuit or part of graph (may be complete graph as well) that visits every edge in G exactly once. That means to complete a visit over the circuit no edge will be visited multiple time. The above image is an example of Hamilton circuit starting from left-bottom or right-top.
A path which is followed to visitEuler Circuit is called Euler Path. That means a Euler Path visiting all edges. The green and red path in the above image is a Hamilton Path starting from lrft-bottom or right-top.
Difference Between Hamilton Circuit and Euler Circuit
|Euler circuit||Hamilton circuit|
|Eulerian circuit traverses every edge exactly once.||Hamilton circuit may repeat edges.|
|Eulerian circuit may repeat vertices.||Hamiltonian circuit visits each vertex exactly once.|
|Path in Euler Circuit is called Euler Path.||Path in Hamilton Circuit is called Hamilton Path.|
|Euler Circuit always follow Euler’s formula V – E + R = 2||Hamilton Circuit also follow Euler’s formula.|
Euler provided a formula about graph which is,
V – E + R = 2
V = Number of Vertices
E = Number of Edges
R = Number of Regions
The hole theorem and there proof is given below:
Theorem: Let P be a convex polyhedron with V vertices, E edges, and R regions. Then V – E + R = 2.
Proof: We will start the proof by choosing a point C inside P. Since P is convex, the line segment joining C to any point inside the polyhedron P, or on P itself, lies entirely within P. Next we choose a radius r so large that the sphere with center C and radius r contains the polyhedron P. Hence the spherical polyhedron is a division of the sphere into F disjoint spherical polygons, which we will call Q1, … , QF.
Let’s apply Girard’s Theorem to the polygon Qi. Actually we will use the extension of Girard’s Theorem to spherical polygons. Let ei denote the number of sides of Qi. Then sum of angles of Qi = (ei – 2) + area(Qi) / r2.
Summing this over the faces we get sum of angles of Qi = (ei-2) +area (Qi) /r2
We will examine each of these sums. In each case we will be able to find the sum by geometric means. Since the spherical polyhedron covers the sphere, at any vertex the angles with that vertex fill out the entire 2 radians.
Thus the angles at each vertex contribute 2 to the sum, and multiplying by the number of vertices we see that the first sum is equal to 2V.
We split the second sum into two sums. (ei-2) = ei –2
The first sum is times the total number of all of the edges of all of the faces. Since we are summing over the faces, each edge of the polyhedron is counted twice in this sum. Therefore, ei = 2E.
The second sum is simply, 2 = 2R
Finally, since the polygons are disjoint and cover the entire sphere we have area (Qi) /r2 = area(S)/r2 = 4.
Putting this all together we get 2V = 2 E – 2 R + 4.
Dividing by 2, and rearranging we get Euler’s formula
V – E + R = 2
Hence, Euler’s Formula is proved.
Mathematical Problem on Euler’s Formula
Count the number of Vertices (V), Edges (E) and Regions (R) of the following map and verify Euler’s Formula.
Number of vertices V = 6
Number of Edges E = 9
Number of Regions R = 5
V – E + R = 2
LHS = 6 – 9 + 5 = 2 (verified).
Hope your experience with this tutorial is quite good. Let’s know your expression through comment. Thanks.