Cheenta
Euleriam Graph
Euleriam Graph
Content
1 Lessons Overview
2 Eulerian Graph
3 Example
4 Planner Graph
5 Euler’s Theorem
6 Problems
1
Euleriam Graph
Lesson Overview
In this lesson we will discuss about Euleriam Graph, Planner graph and Euler’s
theorem on Planner Graph.
Eulerian Graph
An Eulerian path is a path that uses every edge of a graph exactly once. An Euler
path starts and ends at different vertices.
A circuit is called an Eulerian circuit if it visits all the edges of the graph exactly
ones. It begins and ends on the same vertices.
A graph containing an Eulerian circuit is called an Eulerian Graph.
Note
(i) Every Eulerian Graph is a connected graph.
(ii) A connected graph is Eulerian if the degree of all its vertices is even.
2
Euleriam Graph
Example
Graph 1 and Graph 2 are not Eulerian Graph because in Graph 1 all the vertices
are of odd degree and in graph 2 the vertices A and D are of odd degree.
In graph 3 there is an Eulerian circuit
AFDBCADCEBA
So this is an Eulerian Graph.
Planner Graph
A graph that can be drawn in such a way that its edge does not intersect each other
except at their endpoints is called a planner graph.
3
Euleriam Graph
Figure 1
Figure 2
The graph shown in Figure 1 is planner , while the graph shown in Figure 2 is not
planner.
Euler’s Theorem
If a Graph is depicted properly , then it divides the graph into several regions called
faces. Let the number of faces be F , number of vertices be V and the number of
edges be E.
Then Euler’s Theorem states that the quantity V − E + F = 2 always holds true
for a planner graph.
4
Euleriam Graph
Problems
Problem 1: There are 7 lakes in Lakeland. They are connected by 10 canals so
that one can swim through the canals from any lake to any other. How many islands
are there in Lakeland?
Solution : We will consider the points and the vertices of the square as the vertices,
and the segments and the sides of the square as the edges of a planner graph. For each
region (among those into which the graph divides the plane) we calculate the number
of edges on its border. Then we add up all these numbers. Since any edge separates
exactly two different faces from one another, the total must be simply double the
number of edges. Since all the faces are triangles, except for the outer one, which is
surrounded by four edges, we get 3(F − 1) + 4 = 2E; that is, E = 3(F − 1)/2 + 2.
Since the number of vertices equals 24, using Euler’s formula, we have
3(F − 1)
24 − +2 +F =2
2
This gives F = 43 (counting the ”outside face”). So, the number of triangles our
square is divided into is 42 .
5
Euleriam Graph
Problem 2: Prove that for a planner graph 2E ≥ 3F .
Solution : Each face must be surrounded by at least 3 edges. Let B be the total
number of boundaries around all the faces in the graph. Thus we have that 3F ≤ B.
But also B = 2E, since each edge is used as a boundary exactly twice. Putting this
together we get 2E ≥ 3F .
Problem 3: Prove that for a planar connected graph E ≤ 3V − 6.
Solution : From the previous problem 2E ≥ 3F .
Substituting this into Euler’s formula V − E + F = 2
we have V − E + 2E/3 ≥ 2.
That gives E ≤ 3V − 6, as required.
Note
Combining 3V − 6 ≥ E and 2E ≥ 3F
we get 2V − 4 ≥ F
So the number of faces of a Connected Planner graph cannot exceed 2V − 4.
6
Euleriam Graph
Problem 4
Prove that the graph with 5 vertices, each of which is connected by an edge
to every other, is not planar.
Problem 5
Is it possible to build three houses and three wells, then connect each house
with each well by nine paths, no two of which intersect except at their end-
points?
