Graph Theory Course

Chapter II: Cycles

Dr. B. Sidaoui

Sepember 2024

Abstract

This chapter covers the fundamental concepts of graph theory, including cycles,
its decomposition, cyclomatic and cocyclomatic numbers. It also explores the con-
cepts of planar graph, Euler’s proprieties, dual graph, and trees. Additionally, the
chapter discusses different methods of spanning tree.

1
 Chapter II: Cycles

1 Graph decomposition
A decomposition of a graph G = (V, E) is a set of subgraphs H1 , ..., Hk that partition of
the edges of G. Where, ∪1≤i≤k Hi = G and E(Hi ) ∩ E(Hj ) = ∅.

1.1 Cycle decomposition

A cycle or circuit is elementary if all the vertices that compose are distinct. A cycle
decomposition is a graph decomposition where each subgraph Hi in the decomposition is
a cycle. Every cycle is a sum of elementary cycles with no shared edges. Similarly, Every
cocycle is a sum of elementary cocycles without common edges.
Cycle decompositions are used in various applications within graph theory, such as in
the study of Hamiltonian cycles, network design, and in certain optimization problems.

1.2 Cycle basis

A cycle basis (in the vectorial sense) can be defined as a family of cycles that is linearly
independent (all cycles are independent, with none being expressible as a linear combina-
tion of the others) and generating (every cycle can be written as a linear combination of
the cycles in the family). Where, every cycle is represented by a vector.
let G = (V, E) be a directed graph. For a cycle µ, we denote µ+ the set of arcs in the
cycle that follow the correct direction of µ, and µ− the set of arcs in the cycle that follow
the opposite direction of µ. Each cycle can be coded by a vector defined by:

+
 1 if ei ∈ µ

Bµ = −1 if ei ∈ µ− , ei ∈ E (1)

0 otherwise


The elements of the basis are also known as fundamental cycles. Moreover, The
number of elements in the cycle basis (i.e., the dimension of the cycle space) is called the
cyclomatic number of G.

1.2.1 Cyclomatic number

Cyclomatic number, developed by Thomas McCabe, is a metric that measures the com-
plexity of a program by counting its decision points. It measures the number of unique
paths through the code. The word ”cyclomatic” comes from the number of fundamental
(or basic) cycles in connected, it also gives the number of independent paths through
strongly connected directed graphs.
Mathematically, for a directed graph G = (V, E), cyclomatic number M is defined by
the next formula:

SALHI Ahmed University Center of Naâma 2

 Chapter II: Cycles

γ(G) = M –N + P (2)

where: M is the number of edges in the graph, N is the number of nodes in the graph,
and P is the number of connected components. If the graph is connected, the number of
connected components P will be equal to 1. So, the formula can be defined as :

γ(G) = M –N + 1 (3)

1.3 Co-cycle basis

A co-cycle basis (in the vectorial sense) can be defined as a family of co-cycles that is
linearly independent and generating. Where, every co-cycle is represented by a vector. A
co-cycle is elementary if it consists of arcs that connect two connected subgraphs (con-
nected components).
let G = (V, E) be a directed graph. For a cycle µ, we denote ρ its associated co-cycle.
ρ+ is the set of outgoing arcs from the cycle µ and ρ− is the set of incoming arcs into the
cycle µ. Each co-cycle can be coded by a vector defined by:

+
 1 if ei ∈ ρ

Bρ = −1 if ei ∈ ρ− , ei ∈ E (4)

0 otherwise


The elements of the basis are also known as fundamental co-cycles. Moreover, The
number of elements in the co-cycle basis is called the cyclomatic number of G.

1.4 Co-cyclomatic number

The co-cyclomatic number of a graph, also known as the cocycle rank, is defined as the
number of edges that need to be removed to make the graph acyclic (without cycles) or
to reduce the graph to a forest. Mathematically, if G = (V, E) is a connected graph, the
co-cyclomatic number is given by:

λ(G) = M − N + P (5)

where: M is the number of edges in the graph, N is the number of nodes in the graph,
and P is the number of connected components. If the graph is connected, the number of
connected components P will be equal to 1.

SALHI Ahmed University Center of Naâma 3

 Chapter II: Cycles

2 Planar graph
When a connected graph can be drawn without any edges crossing, it is called planar.
When a planar graph is drawn without edges crossing, the edges and vertices of the graph
divide the plane into regions called faces.

2.1 face
In a planar graph, a face refers to a region of the plane that is bounded by edges (or arcs)
of the graph. Indeed, there are two type of faces: The region that extends infinitely and
is not enclosed by any edges is known as the exterior or infinite face, and any other region
bounded by edges is considered an interior face.

2.2 Euler’s Formula

Consider a connected planar graph G = (V, E) with N vertices, M edges, and F faces.
Euler demonstrated the following properties.

• Property 1: For any connected planar graph G = (V, E), we have N − M + F =

2. And more generally, every planar graph with k connected components satisfies
N − M + F = 2k.

• Property 1: For a simple planar graph (no loops, no multiple edges) with |V | ≥ 3,
because at least 3 edges bound every face and each edge borders at most 2 faces,
combining this with Euler’s formula, we obtain:

3|F | ≤ 2|E| → |E| ≤ 3|V | − 6

If the graph has no 3-cycles (triangle faces), then each face is bounded by at least
4 edges, giving:
4|F | ≤ 2|E| → |E| ≤ 2|V | − 4

• Property 2: The maximum number of edges of a planar graph G = (V, E), with
N vertices and a smallest face bounded by P ≥ 3 edges, is PP−2 ∗ (N − 2).

2.3 Kurathoski’s Theorem

A graph is planar if and only if it does not contain a subgraph that is a subdivision of K5
(a complete graph on five vertices) or K3,3 (a complete bipartite graph on six vertices).

SALHI Ahmed University Center of Naâma 4

 Chapter II: Cycles

2.3.1 Proof

The proof is by contradiction. So assume that K5 is planar. Then the graph must satisfy
Euler’s formula for planar graphs.
A graph K5 has 5 vertices and 10 edges, so we get 5 − 10 + f = 2, which says that
if the graph is drawn without any edges crossing, there would be 7 faces. At least three
edges bound each face, so we have:

|E| ≤ 3|V | − 6 → 10 ≤ 3 ∗ 5 − 6 → 10 ̸≤ 9

The proof is by contradiction. So assume that K3,3 is planar. Then the graph must
satisfy Euler’s formula for planar graphs.
A bipartite graph K3,3 has 6 vertices and 9 edges, so we get 6 − 9 + f = 2, which says
that if the graph is drawn without any edges crossing, there would be 5 faces. At least
three edges bound each face, so we have:

|E| ≤ 3|V | − 6 → 9 ≤ 3 ∗ 6 − 6 → 9 ≤ 12

|E| ≤ 2|V | − 4 → 9 ≤ 2 ∗ 6 − 4 → 9 ̸≤ 8

3 Dual Graph
An important property of planar graphs is that they always have a dual graph, where
each face of the original graph G corresponds to a vertex in the dual graph G∗ , and the
edges are defined by the adjacency relationships between the faces in the primal graph.
The figure below presents an example of a planar graph and its dual.

Figure 1: The blue graph is the primal graph, and the red graph is its dual graph

SALHI Ahmed University Center of Naâma 5

 Chapter II: Cycles

4 Tree and forest

A tree is an undirected, connected graph with no cycles. By definition, a tree is always a
simple graph or 1-graph.
Trees in graph theory have several important properties such as:

• Acyclicity : A tree has no cycles.

• Connectivity : A tree is always connected, meaning there is a path between any

two vertices in the tree.

• Unique path: There is exactly one path between any two vertices in a tree.

• Number of edges: A tree with N vertices has exactly (N − 1) edges.

• Adding or removing edge : If you add an edge to a tree, it creates exactly one
cycle. Conversely, removing any edge from a tree will make the graph disconnected.

• Leaves : In a tree, any vertex with degree 1 is called a leaf. Every tree with at
least two vertices has at least two leaves.

• Spanning tree : A spanning tree of a connected graph is a subgraph that is itself

a tree. Every connected graph has at least one spanning tree.

• Max or Min spanning tree : In weighted graphs, a minimum (or maximum)

spanning tree is a spanning tree that minimizes (or maximizes) the total weight of
its edges.

4.1 Binary tree

A binary tree is a type of tree data structure in which each node can have at most two
child nodes, known as the left child and the right child.
The structure of the binary tree is composed of:

1. Root : A binary tree has a unique initial node called the root of the tree.

2. Left child : The node to the left of the root is called its left child.

3. Right child : The node to the right of the root is called its right child.

A binary tree in which all the leaves are on the same level and every non-leaf node
has two children, is called full binary tree, as shown in the following figure.

SALHI Ahmed University Center of Naâma 6

 Chapter II: Cycles

Figure 2: Binary tree graph

4.2 Forest
In graph theory, a forest is an undirected, disconnected, acyclic graph. In other words, a
disjoint collection of trees is known as forest. Each component of a forest is tree.

4.3 Arborescence
A directed graph G = (V, E) is called an arborescence if, from a given node x known
as the root node, there is exactly one elementary path from x to every other node y
(y ∈ V − {x}). In summary, an arborescence is essentially a directed version of a tree
with a specified root, where all nodes are connected through unique paths originating
from that root.

5 Spanning tree
A spanning tree is a subset of graph G = (V, E), such that all the vertices are connected
using minimum possible number of edges. Hence, a spanning tree does not have cycles
and a graph may have more than one spanning tree. The objective in a spanning tree
of a graph is to connect the vertices with the minimum possible cost (or the maximum
values). The total number of spanning trees with N vertices that can be created from a
complete graph is equal to N (N − 2).
Basically, a spanning tree is used to find a minimum path to connect all nodes of the
graph. Minimum spanning tree can be used to design water-supply networks, telecom-
munication networks, computer network, electrical grids, etc.

6 Minimum spanning tree

A minimum spanning tree is defined as a spanning tree where the sum of the edge weights
is minimized. The total weight of the spanning tree is the sum of the weights assigned

SALHI Ahmed University Center of Naâma 7

 Chapter II: Cycles

to its edges. In practical applications, this weight might represent distance, traffic load,
congestion, cost, or any other relevant value
There are various algorithms to determine the minimum spanning tree of a given
graph, some of the most common ones include: Krushkal’s algorithm, Prim’s algorithm,
and Boruvka’s algorithm.

6.1 Algorithm of Krushkal

Kruskal’s algorithm is a popular method for finding the minimum spanning tree (MST)
of a connected, undirected graph. MST algorithm is to connect all the vertices of a graph
with the minimum total edge weight while avoiding cycles. It follows a greedy approach
by selecting edges in increasing order of weight and ensuring no cycles are formed. In
next, the step-by-step outline of Kruskal’s algorithm:

1. Sort all edges: Start by sorting all the edges in the graph by their weights.
2. Initialize the MST: Create an empty set to hold the edges of the minimum span-
ning tree.
3. Process edges: Iterate through the sorted list and perform the following steps:
• For each edge, check if adding it to the MST would create a cycle. If the edge
doesn’t form a cycle, include it in the MST, else discard it.
4. Termination: Continue this process until the MST contains exactly V − 1 edges,
where V is the number of vertices in the graph.
5. Output: The set of selected edges represents the minimum spanning tree.

6.1.1 Kruskal’s algorithm code

1. Input: A connected, weighted and undirected graph G = (V, E, W ).

2. Initialization:
• Sorting edges by their weights, W (e1 ) ≤ ... ≤ W (em ).
• V ′ = {∅}; Cost = 0; m = |E|; E ′ = {e}/ e = arg min{W (ek )/k = 1..m};
3. Iteration:
• for i=1 to m do
– if (E ′ ∪ ei ) doesn’t contain a cycle then, where ei ∈ E.
∗ E ′ = E ′ ∪ ei ;
∗ Cost = Cost + W (ei );
– end
• end
4. Output: Return a MST G = (V ′ , E ′ , W ′ ).

SALHI Ahmed University Center of Naâma 8

 Chapter II: Cycles

6.2 Algorithm of Prim

Prim’s algorithm is a classic method used to find the Minimum Spanning Tree (MST) of
a connected, undirected graph. Unlike Kruskal’s algorithm, which starts with edges, in
Prim’s algorithm, MST is constructed incrementally by starting with a single vertex and
progressively expanding the tree by adding the nearest neighboring vertex at each step.
In the following, the step-by-step outline of Prim’s algorithm:

1. Initialize the MST: Start with any arbitrary vertex as the initial vertex of the
tree.
2. Process edges: Repeat this process until all the vertices are included in the MST.
• Checks for the minimum edge weight that connects one vertex of MST to
another vertex that is not yet in the MST.
• Add the chosen edge to the MST if it doesn’t form any cycle.
3. Output: The set of selected edges represents the minimum spanning tree.

6.2.1 Prim’s algorithm code

1. Input: A connected, weighted and undirected graph G = (V, E, W ).

2. Initialization:
• selecting an arbitrary vertex x ∈ V .
• We suppose: V ′ = {x}; E ′ = {∅}; Cost = 0; m = |E|;
3. Iteration:
• for i=1 to m do
– ei = min{(xi , xj )/xi ∈ V ′ , xj ∈ {V − V ′ }}; and doesn’t form a cycle.
– E ′ = E ′ ∪ ei ;
– Cost = Cost + W (ei );
• end
4. Output: Return a MST G = (V ′ , E ′ , W ′ ).

6.3 Algorithm of Boruvka

Borůvka’s algorithm is one of the is one of the oldest minimum spanning tree algorithms.
The algorithm works by iteratively building the minimum spanning tree, starting with a
forest (each vertex is considered as a tree).
In each iteration, the algorithm finds the minimum weighted edge that connects a tree
to another tree, and adds that edge to the minimum spanning tree. Below is a complete
algorithm.

SALHI Ahmed University Center of Naâma 9

 Chapter II: Cycles

1. Input: A connected, weighted and undirected graph G = (V, E, W ).

2. Initialization:
• T reek = Vk /k = 1..N, Vk ∈ V .
• F = ∪k=1..N {T reek }
• V ′ = {∅}; E ′ = {∅}; Cost = 0;
3. Iteration:
• While (size(F ) ̸= 1)
– e = min{(ei , ej )/ei , ej ∈ F ;
– E ′ = E ′ ∪ e;
– Cost = Cost + W (e);
• end
4. Output: Return a MST G = (V ′ , E ′ , W ′ ).

6.4 Exercise
Determine the minimum and maximum spanning trees of the graph shown in the following
figure using the three algorithms discussed below.

Figure 3: Weighted and undirected graph

SALHI Ahmed University Center of Naâma 10