Walks and their classification
❖ A walk of a graph is an alternating sequence 𝑣0𝑒1𝑣1𝑒2𝑣2 … 𝑣𝑛−1 𝑒𝑛𝑣𝑛 of vertices and edges
beginning and ending with the vertices. It is denoted by w.
❖ The number of edges present in a walk is called its length.
❖ In a walk, a vertex or an edge can appear more than once.
❖ If a walk begins and ends with a same vertex, then walk is called as a closed [Link],
it is called open walk.
❖ If in an open walk, no edge appears more than once , then the walk is called a trail .
❖ A closed walk in which no edge appears more than once is called a circuit.
❖ A closed trail is called a circuit.
❖ A trail in which no vertex appears more than once is called a path.
❖ A circuit in which the terminal vertex does not appear as an internal vertex and no internal vertex is
repeated is called a cycle.
❖ Closed path is a cycle.
.
Note: All 𝑣𝑖′𝑠 and 𝑒𝑖′𝑠 need not be distinct. In this 𝑣0 − 𝑣𝑛 walk, 𝑣0 is the initial vertex and
𝑣𝑛is the end vertex. Other vertices are internal vertices. Length of the walk is thenumber of edges
in 𝑤.
Example: 1
v5
𝑣1𝑒1𝑣2𝑒2𝑣3𝑒3𝑣5𝑒5𝑣2 is a walk of length 4.
𝑣4𝑒4𝑣5𝑒5𝑣2𝑒5𝑣5𝑒4𝑣4 is a walk of length 4.
𝑣1𝑒1𝑣2𝑒5𝑣5is a walk of length 2.
Example: 2
Connected and disconnected graphs:
Two vertices in G are said to be connected if there is atleast one path from one vertex to the other.A
graph G is a connected graph if every pair of distinct vertices in G are [Link], G is called
a disconnected graph.
Example: (2)
(1)
(3) (4)
(1) , (2) – Connected graphs (3), (4) – disconnected graphs
Component of a graph:
Every graph G consists of one or more connected graphs. Each connected graph is a sub graph of G and is
called component of G. The number of components in a graph G is denoted by 𝐾(𝐺).
Example:
K(G) = 5
Euler circuits:
Consider a connected graph G. If there is circuit in G that contains all the edges of G, then that circuit is
called an Euler circuit or Eulerian line or Euler tour in G.A connected graph that containing an Euler
circuit is called an Euler graph or Eulerian graph. Example:
Euler trails:
Consider a connected graph G. If there is trail in G that contains all the edges of G, then that trail is called a
Euler trail or unicursal line. A connected graph that contains a Euler trail is called a semi-Euler graph or semi-
Eulerian graph.
Hamilton cycle:
Let G be a connected graph. If there is a cycle in G that contains all the vertices of G, then that
cycle is called a Hamilton cycle in G. A graph that contains a Hamilton cycle is called
a Hamilton graph or Hamiltonian graph.
Hamilton cycle must include all the vertices of G. This does not mean that it should include all
the edges of G.
Hamilton Path
A path (if any) in a connected graph which includes every vertex (but not necessarily every edge) of
the graph is called a Hamilton path (or Hamiltonian path) in the graph.
Example:
(i) Cycle ABDCA – Hamilton cycle
(ii) Path ABDC – Hamilton Path