Department of Mathematics Elementary Graph Theory Lecture 6
Basic Properties
Walk
A walk is an alternating sequence of vertices and edges of a graph.
Vertex can be repeated
Edges can be repeated
Open walk
A walk is said to be an open walk if the starting and ending vertices are
different.
Closed walk
A walk is said to be closed walk if the starting and ending vertices are
identical.
Trial
A walk with no repeated edges is called trial.
Circuit
A circuit is a closed walk that does not contain any repeated edges.
Path
Is a trial in which neither vertices nor edges are repeated.
Cycle
Is a circuit in which the vertices does not repeated.
A graph
v2v1v3v1v4v1v5v7 is a v2 v7 walk and it is open , v2v1v3v1v5v7 v5v2 is a closed walk
Dr. Didar A. Ali 1
, Department of Mathematics Elementary Graph Theory Lecture 6
v2 v1v3v4v1v5v7 is a v2 v7 trial
v2v3v1v5v6v7 v5v4v1v2 is a closed trial (is a circuit)
v2 v3v1v4 v5v6v7 is a v2 v7 path , v2v5v7 also is a v2 v7 path
v2v1v5v4v3v2 is a closed path ( is a cycle)
Geodesic
A shortest v2 v7 path is called geodesic
Connected graph
A graph G is said to be connected graph, if every pair of vertices of a graph G
is joined by a path. Otherwise G is disconnected.
Connected graph Disconnected graph
Component
A maximal connected subgraph of G is called component, thus disconnected
graph has at least two components.
Length
The length of a walk, trial, path or cycle is its number of edges.
Distance
The distance between two vertices u and v in a graph G is the minimum
lengths of all u-v path in G, and it is denoted by dG (u , v) . If no u-v path
exists, then dG (u , v) .
Girth
The girth of a graph G is the length of a shortest cycle and is denoted by
gir (G ) .
Circumference
The circumference of a graph G is the length of a longest cycle and is denoted
by c (G )
Dr. Didar A. Ali 2
Basic Properties
Walk
A walk is an alternating sequence of vertices and edges of a graph.
Vertex can be repeated
Edges can be repeated
Open walk
A walk is said to be an open walk if the starting and ending vertices are
different.
Closed walk
A walk is said to be closed walk if the starting and ending vertices are
identical.
Trial
A walk with no repeated edges is called trial.
Circuit
A circuit is a closed walk that does not contain any repeated edges.
Path
Is a trial in which neither vertices nor edges are repeated.
Cycle
Is a circuit in which the vertices does not repeated.
A graph
v2v1v3v1v4v1v5v7 is a v2 v7 walk and it is open , v2v1v3v1v5v7 v5v2 is a closed walk
Dr. Didar A. Ali 1
, Department of Mathematics Elementary Graph Theory Lecture 6
v2 v1v3v4v1v5v7 is a v2 v7 trial
v2v3v1v5v6v7 v5v4v1v2 is a closed trial (is a circuit)
v2 v3v1v4 v5v6v7 is a v2 v7 path , v2v5v7 also is a v2 v7 path
v2v1v5v4v3v2 is a closed path ( is a cycle)
Geodesic
A shortest v2 v7 path is called geodesic
Connected graph
A graph G is said to be connected graph, if every pair of vertices of a graph G
is joined by a path. Otherwise G is disconnected.
Connected graph Disconnected graph
Component
A maximal connected subgraph of G is called component, thus disconnected
graph has at least two components.
Length
The length of a walk, trial, path or cycle is its number of edges.
Distance
The distance between two vertices u and v in a graph G is the minimum
lengths of all u-v path in G, and it is denoted by dG (u , v) . If no u-v path
exists, then dG (u , v) .
Girth
The girth of a graph G is the length of a shortest cycle and is denoted by
gir (G ) .
Circumference
The circumference of a graph G is the length of a longest cycle and is denoted
by c (G )
Dr. Didar A. Ali 2
