Outline of Presentation
✓Walk
✓Trail
✓Path
✓Cycle
✓Distance
✓Eccentricity
✓Diameter
WALK
Walk is sequence of adjacent vertices (or edges)
in a graph.
1 – 2 – 4 – 5 – 3 is a walk from
1 to 3
1 – 2 – 3 -– 4 – 5 – 3 is a walk
from 1 to 3
1 – 2 – 3 – 1 – 2 – 4 – 5 – 3 is a walk
from 1 to 3
Note: A walk can contain vertices and edges
multiple times.
In any graph, the number of vertices of odd degree is even.
TRAIL
Trail is an open walk where vertices can
repeat, but not edges.
1 – 2 – 3 – 4 – 5 – 3 is a trail from
1 to 3.
1 – 2 – 3 – 4 – 5 – 3 – 1 is a closed
trail.
PATH
Path is an open walk with no repetition of
vertices and edges.
1 – 2 – 3 – 4 – 5 is a path
from 1 to 5.
1 – 2 – 4 – 5 – 3 is a path
from 1 to 3.
CIRCUIT
Circuit is a closed walk where vertices can
repeat, but not edges.
1 – 2 – 3 – 4 – 5 – 3 – 1 is a
circuit.
1 – 3 – 5 – 4 – 3 – 2 – 1 is a
circuit.
CYCLE
Cycle is a closed walk where neither vertices nor
edges can repeat. But since it is closed, the first
and the last vertices are the same (one
repetition).
1 – 2 – 4 – 5 – 3 – 1 is a
cycle.
1 – 3 – 5 – 4 – 2 – 1 is
a cycle.
DISTANCE
Distance
between two
vertices in a
graph is the
number of
edges in a
shortest path
connecting
them.
ECCENTRICITY
It is defined as the maximum distance of one vertex
from other vertex. It is denoted by e(V).
DIAMETER of graph
The diameter of graph is the maximum
distance between the pair of vertices.
Way to solve :
Find eccentricity of all vertices and then find
maximum of all.
Regular graph
• If each vertex of a graph G has the same degree as every
other vertex.
• A k- regular graph is a graph whose common degree is k.
Example: Consider k2 and k4. The degree of each vertex in k2
regular graph is 2 and k4 regular graph is 4. Hence k2, k4 are
regular graphs.
15
Complete graph
• A simple graph in which there is exactly one edge between
each pair of distinct vertices is called a complete graph. In a
complete graph, every pair of vertices are adjacent.
17
Planar Graphs
A graph is said to be planar if it can be drawn in a plane
such that no two edges cross each other.
Non-Planar Graphs
A graph is said to be non-planar if it can be drawn in a
plane such that two edges cross each other.
18
Maps
A particular planar representation of a finite planar
multigraph is called a Map.
Region
The map so drawn divides the plane into various areas
bounded by edges which cannot be further subdivided.
20
i) Infinite Region
If the area of the region is infinite, then that region is
called infinite region.
In the above figure, we have R4 to be the infinite
region.
ii) Finite Region
If the area of the region is finite, then that region is called
finite region.
In the above figure, R1, R2 & R3 are finite region and R4 is
infinite region.
iii) Degree of Region
If G is a planar graph and R be its region, then number of
edges in boundary of R is defined as degree of region R.
In the above figure, deg (R1) = 3, deg (R2) = 3, deg(R3) = 3
and deg(R4) = 5.
Note: Degree of a cut edge is counted twice.
23
Properties of Planar graphs
• If a connected planar graph G has E edges and R regions, then R ≤
2/3 E.
• If a connected planar graph G has E edges, V vertices and R
regions then V - E + R = 2 (Euler’s Formula)
• If a connected planar graph G has E edges and V vertices, then
3V – E ≥ 6.
• A complete graph Kn is planar, if and only if n < 5.
24
Question:
Is the complete graph K4 planar ?
Solution:
25
The complete graph K4
contains 4 vertices and 6
edges.
From the property, 3V – E ≥ 6,
hence 3 * 4 – 6 = 6, which
satisfies the property of
planar graphs.
Therefore, K4 is a planar
graph.
• V - E + R = 2 (Euler’s Formula)
Pseudo-graph
• The graphs in which loops and parallel edges are allowed.
29
Weighted graph
• The graph in which weights are assigned to each
edge.
30
Traversable graphs
• A graph is traversable if you can draw a path between all
the vertices without retracing the same path.
31
EULER’S FORMULA
A formula which is used to check the planarity of the given graph is called Euler’s formula.
The general formula is :
|V|-|E|+ |R| = 2
Where, V is the number of vertices in the graph.
E is the number of edges in the graph.
R is the regions in the graph.
In this graph, there are total 5 vertices,10 edges,7 region
i.e. V = 5, E=10, R=7
So, by Euler’s formula
|V|-|E|+ |R| =2
5 - 10 + 7 = 2
i.e. LHS = RHS
