J. Nig. Soc. Phys. Sci. 4 (2022) 844

Journal of the
Nigerian Society

of Physical
Sciences

Graph Theory: A Lost Component for Development in Nigeria

Olayiwola Babarinsa∗

Department of Mathematics, Federal University Lokoja, Kogi State, Nigeria

Abstract

Graph theory is one of the neglected branches of mathematics in Nigeria but with the most applications in other fields of research. This article
shows the paucity, importance, and necessity of graph theory in the development of Nigeria. The adjacency matrix and dual graph of the Nigeria
map were presented. The graph spectrum and energies (graph energy and Laplacian energy) of the dual graph were computed. Then the chromatic
number, maximum degree, minimum spanning tree, graph radius, and diameter, the Eulerian circuit and Hamiltonian paths from the dual graph
were obtained and discussed.

DOI:10.46481/jnsps.2022.844

Keywords: Adjacency matrix, Laplacian matrix, dual graph, graph spectrum, graph energy.

Article History :
Received: 31 May 2022
Received in revised form: 10 July 2022
Accepted for publication: 11 July 2022
Published: 20 August 2022

c© 2022 The Author(s). Published by the Nigerian Society of Physical Sciences under the terms of the Creative Commons Attribution 4.0 International license
(https://creativecommons.org/licenses/by/4.0). Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.

Communicated by: S. Fadugba

1. Introduction

The mathematical structures used to model pairwise relation-
ships between things are studied in graph theory. Graph theory
has applications in natural science, management and social sci-
ences, arts and agricultural science, engineering and medicine,
and information systems [1, 2]. It is the key subject essentially
in mastering data science and is widely adopted by tech giants
like Google, Amazon, Meta, Apple, and Microsoft.
The considerable origin of graph theory emanated from the
problem of the Konigsberg bridges [3]. The city Konigsberg
(now Kaliningrad in Western Russia) has two islands and main-
lands with seven bridges connecting the lands. The challenge
was to leave a point (home) and traverse each bridge exactly
once and return to the same point [4, 5], see Figure 1.

∗Corresponding author tel. no: +2348060032554
Email address: olayiwola.babarinsa@fulokoja.edu.ng (Olayiwola

Babarinsa )

Figure 1. The bridges of Konigsberg.

In 1736, Swiss mathematician Leonhard Euler took up the
problem of the seven bridges of Konigsberg and reconstructed
it in a dual graph where the two mainlands and the two islands
represent vertices and the seven bridges represent the edge (see
Figure 2) and concluded that the task was not possible to do
[6, 7]. His method of the proof of Konigsberg bridges leads to
the concept of the Eulerian graph and to the introduction of a
new branch of mathematics called graph theory.

1



Babarinsa / J. Nig. Soc. Phys. Sci. 4 (2022) 844 2

Figure 2. A graph representation of the bridges of Konigsberg.

In 1840, the development of graph theory started when Ger-
man mathematician Ferdinand Mobius presented the idea of a
complete graph and bipartite graph [8]. In 1852, a Scottish di-
vine Francis Guthrie found the famous four-colour theorem [9].
Over two decades, the term ”graph” was coined in 1878 by En-
glish mathematician Joseph Sylvester. He represented it as par-
titions of numbers by nodes placed in order at the points of a
rectangular lattice [9].

This paper is organized into sections. In section 2, basic
graph terminologies and illustrations are given, and in section
3, we discuss the impact of graph theory and its applications
with examples emanating from Nigerian settings. Then the ad-
jacency matrix and Laplacian matrix, and representation of the
(Nigeria) map graph were computed and visualized, and the re-
sults were discussed.

2. Preliminary and Background in Graph Theory

Graphs harmonize vertices and edges that connect these ver-
tices. This definition and its terminologies will be meaningless
to researchers who want to pick up research interest in graph
theory or to apply its usefulness in other research areas without
understanding the rudimentary subject matter. It is important to
note that an edge is an ambiguous word that may refer to both
undirected edges and directed edges. Readers should be aware
that in this paper whenever an ”edge” and a ”graph” are men-
tioned, they are referring to an undirected edge and a simple
graph respectively, except otherwise stated.

2.1. Graph Models
To model a graph, there must exist an interaction. The inter-
action may be a mutually exclusive interaction (called an undi-
rected edge) or just one-way interaction (called a directed edge
or arc). Now, consider two or more objects (we say they are
”vertices” or ”nodes”) and the interactions or connections be-
tween these objects are referred to as edges. We are much inter-
ested, in the diagrams, whether two given vertices are joined by
a line (edge or arc) but the way they are joined is less important.
For instance, Facebook users are vertices and their friendships
are the edges, proteins are vertices and their interactions are
edges, two or more elements are vertices and their bonds are the
edges, particles are vertices and their collisions are the edges,
footballers on the pitch are vertices and the passes made with
the ball are the edges, dating apps/websites connecting people
(vertices) by their interests (edges).

Problems in almost every conceivable discipline can be
solved using graph models. Graphs are widely used to describe
the acquaintanceships between people, phone calls between two

or more lines, links between websites, a collaboration between
researchers, roadmaps, assignment of jobs, coloring (minimum
color) the regions of a map, differentiating between isomers,
food chain and food web, Sequencing of DNA, finding the
shortest path between two cities, communication link between
computers (mesh network), scheduling exams and assigning
channels to television stations [2]. Some of the modeled graphs
are acquaintanceship and friendship graphs, influence graphs,
collaboration graphs, call graphs, molecular graphs, web graph
and citation graphs, module dependency graphs, precedence
graphs, concurrent processing, airline routes and road networks,
tournaments, Niche overlap graphs in ecology and protein in-
teraction graphs [2, 10]. These graph models can be created
and visualized using graph software such as NetworkX, Gephi,
GraphViz, Sage, or MATLAB.

2.2. Graphs Definition
To define a simple graph to a non-graph theorist one needs to
”unconventionally” illustrate it. For instance, a tug of war be-
tween two people is a simple graph with two vertices (people)
and an edge (rope), see Figure 3.

Figure 3. A simple graph: Tug of war between two people.

A simple graph is an undirected (non-directed) graph but
if the edges have direction, then it is called a directed graph,
mostly known as a digraph [11]. For example, see Figure 4,
only the rag doll (v1) exerts a greater force (arc) to pull a box
(v2).

Figure 4. A directed graph: A rag doll pulling a box.

The directed edges (arcs or arrows) of a digraph have head
ends and tail ends, see Figure 5. An in-degree, deg−(v), is
the number of arcs (head ends ) towards a particular vertex,
otherwise, it is an out-degree, deg+(v). A vertex that consists
of zero deg−(v) is termed a source and a sink is a vertex with
zero deg+(v) [12].

Figure 5. The head and tail end of an arc.

2



Babarinsa / J. Nig. Soc. Phys. Sci. 4 (2022) 844 3

In addition, if there exist both undirected edges and directed
edges in a graph then the graph is referred to as a mixed graph
[13]. let us consider a weight lifter (v3) with his hands exert-
ing pressure (arcs) in balancing (edge) two ends (v1 and v2) of
weight, see Figure 6.

Figure 6. A mixed graph: A man lifting weight.

Mathematically, a simple graph G = (V,E) consists of a set
of vertices V and a set of undirected edges E [14]. A directed
graph (or a digraph) is a graph that contains only a set of di-
rected edges with the set of vertices V [2]. A mixed graph
G = (V,E,A) is an ordered triple consisting of a set of vertices
V = {v1,v2...vn}, a set of undirected edges E = {e1,e2...en},
and a set of directed edges A [13, 15].

2.3. Graphs Classification
In considering the type of graph to use, one must know if the
graph is directed or undirected, weighted or not weighted, and
sometimes if it is cyclic or acyclic. Another thing to consider
about a graph is whether loops are permitted. A loop (or buckle)
is an edge that links a vertex to itself. A pendant is a vertex that
joins exactly one other vertex.

An edge connects the vertices that define it. A graph with
a countable number of vertices is termed a finite graph, and if
the vertices are infinitely many is called an infinite graph [2].
A weighted graph or edge-labeled graph has edges (directed
or undirected) having a non-negative value called weight. An
unweighted graph can be considered a weighted graph if each of
the edges has a numerical value of weight 1 [16]. The number
of vertices (nodes or points) in G, written as v(G), is the order
of a graph while the number of edges in graph G, written as
e(G), is the size of a graph [17]. A vertex of degree zero is
called isolated. With the terms and definitions, graphs can be
classified based on the types, see Table 1 and Figure 7.

Simple graph. Multigraph. Pseudograph.

Directed graph. Directed multigraph. Mixed graph.

Figure 7. Graph classification.

2.4. Types of Graphs
Many complex graphs (such as network graph) have fundamen-
tal underlaying structure The following are the types of graphs
in graph theory:

Complete graph. Cyclic graph. Wheel graph. Planar graph.

Bipartite graph. Regular graph. Star graph. Path graph.

Weighted graph. Mixed hourglass. Acyclic (Tree). Acyclic (For-
est).

Trivial graph. Euler graph. Halmitonian graph. Null graph.

Hypercube graph. Infinite graph. Connected graph. Friendship graph.

Figure 8. Basic graph types.

2.5. Matrices: Graph representations
Two types of matrices are mostly used to represent graphs; the
adjacency matrix and incidence matrix. The adjacency ma-
trix, A(G) = [ai, j], is an n×n matrix indexed by the vertices
{v1,v2...vn} given as, see for instance

ai, j =

{
1 if viv j is an edge of G
0 otherwise.

(1)

The adjacency matrix can determine if the graph is con-
nected or not by checking the shortest path for every pair
of vertices. The incidence matrix: Let G = (V,E) such that
{v1,v2...vn} are the set of vertices and {e1,e2...em} the set of
edges, then M = [mi, j] is an n×m matrix defined as [18]

mi, j =

{
1 when edge e j is incident with vi
0 otherwise.

(2)

Graph spectrum is the set of graph eigenvalues of A(G) [8].
This spectrum can be used to obtain graph energy. Ivan Gut-
man introduced the concept of graph energy of a simple graph

3



Babarinsa / J. Nig. Soc. Phys. Sci. 4 (2022) 844 4

Table 1. Summary of graph classification

Graph classification Graph type Edges Multiple Edges? Loops?

Weighted or unweighted
Simple graph Undirected No No
Multigraph Undirected Yes No

Directed or undirected
Pseudograph Undirected Yes Yes

Directed graph Directed No No

Cyclic or acyclic
Directed multigraph Directed Yes Yes

Mixed graph Directed and undirected Yes Yes

from theoretical chemistry [19]. Nikiforov [20] gave the ex-
tended concept of graph energy to any matrix. Therefore, en-
ergy of a graph E(G) is the sum of absolute values of eigenval-
ues, λi(G); i = 1,2,...,n, of A(G) [21]. That is,

E(G) =
n

∑
i=1
|λi(G)|. (3)

Some of the forms of matrices used in graph theory are the
degree matrix and (Signless) Laplacian matrix [22]. A degree
matrix, D(G) = [di, j], is an n×n diagonal matrix defined as

di, j =

{
1 deg(vi) if i = j
0 otherwise.

(4)

Furthermore, the Laplacian matrix, L(G) = D(G)−A(G),
has spectrum that consist of µi; i = 1,2,...,n such that
µ1(L(G)) ≥ µ2(L(G)) ≥ ... ≥ µn(L(G)) ≥ 0, where L(G) is
symmetric and positive semidefinite [23]. The Laplacian en-
ergy is defined as

LE(G) =
n

∑
i=1

∣∣∣∣µi −
(

2×edges
vertices

)∣∣∣∣. (5)
A graph G with n vertices is hyperenergetic if E(G) > 2n−2,
hypoenergetic if E(G) < n and non-hypoenergetic if E(G) ≥ n
[24, 10]. Applications of graph energies are pattern recogni-
tion, object identification, face recognition, image analysis and
processing which are widely adopted by military and police
[25, 26]. In the area of medicine, attempts has been made to
use it in neuronal network and epidemics see [27] and the ref-
erences therein.

3. Graph Theory and Nigeria

In this section, the paucity of graph theory and representation
of the Nigeria map (all 36 states and F.C.T) are presented, and
the results are discussed.

3.1. The paucity of Graph Theory Applications in Nigeria
A graph theorist, a boundless researcher, has the most edge for
collaboration. Thus, it will be difficult, if not impossible, to
mention fields where graph theory is not applicable. In Nige-
ria, graph theory is one of the aspects of discrete mathematics
that has not been considered beyond undergraduate and post-
graduate studies, as an elective course, in mathematics, com-
puter science, and engineering. The few published articles from

Nigerian researchers that mentioned graph theory only made
references to the terms that apply to the research interest of the
authors. Presently, no Nigerian mathematician has taken graph
theory, especially graph energy, as his/her research interest, ex-
cept perhaps the author of this paper whose Erdos number and
Dijkstra number are 4 and 5 respectively, see reference in [28].

In the Nigeria setting, for instance, linking BVN to many
bank accounts or NIN to SIM registration is achievable by
graph theory. In today’s Nigerian politics, graph theory is an
essential tool for political analysis. We unconsciously apply
graph theory in our daily activities such as the shortest distance
we take to get to our destinations. The shortest distance usu-
ally has weights, and the weighted graph has huge applications
in transportation systems. Almost every ministry in Nigeria
such as NCC, NCDC, NIPOST, WAEC, NHIS, CBN, FAAN,
FHA, INEC, NBS, NPA, and NPC can deploy graph theory
for the effective performance of the agency in terms of data
collection, analysis, and prediction. Besides, one of the great-
est uses of graph theory in Nigeria is in town planning but it
is not fully utilized. The paucity of graph usage can be seen
in almost all sectors and places in Nigeria. For example, let
us consider the chaotic urbanization of Lokoja (with an area
of 3,180km2) where two major equipped government hospi-
tals (Kogi State Specialist Hospital and Federal Medical Centre
Lokoja) are 2km apart of 3 minute’s drive. It is obvious that in
the planning of the establishment of these hospitals, a sudden
cardiac arrest of a patient was not considered for the outskirt
residents of Lokoja nor of other bordering local government ar-
eas. Another chaotic planning in Lokoja is the two tertiary insti-
tutions (Kogi State polytechnic and Federal University Lokoja),
where the two institutions are about 8.3km apart on 6 minute’s
drive. Furthermore, emergency exits during natural disasters
(such as a flood) or terrorist attacks are not considered in plan-
ning the state capital with three entrance/exit roads that con-
sist of only two roads (Lokoja-okenne/Abuja-Lokoja road and
Ganaja/Lokoja-Ajaokuta road) which lead to Lokoja. Thus, the
cons of the urbanization of Lokoja outweigh its pros.

This catastrophic planning can be found in each state of the
country. Another deficiency of graph theory in Nigeria can
be noticed in the examination timetable scheduling or lecture
timetable in the Nigerian tertiary institutions. Students often
complain of having two or three examinations in a day and
sometimes two examinations at the same time. To solve the
problem of scheduling examination timetables, graph coloring
should be applied.

4



Babarinsa / J. Nig. Soc. Phys. Sci. 4 (2022) 844 5

Table 2. Adjacency matrix of states (and F.C.T) in Nigeria.
v∗1 v

∗
2 v

∗
3 v

∗
4 v

∗
5 v

∗
6 v

∗
7 v

∗
8 v

∗
9 v

∗
10 v

∗
11 v

∗
12 v

∗
13 v

∗
14 v

∗
15 v

∗
16 v

∗
17 v

∗
18 v

∗
19 v

∗
20 v

∗
21 v

∗
22 v

∗
23 v

∗
24 v

∗
25 v

∗
26 v

∗
27 v

∗
28 v

∗
29 v

∗
30 v

∗
31 v

∗
32 v

∗
33 v

∗
34 v

∗
35 v

∗
36 v

∗
37

v∗1 0 0 1 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
v∗2 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
v∗3 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
v∗4 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
v∗5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0
v∗6 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
v∗7 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0
v∗8 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
v∗9 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
v∗10 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
v∗11 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
v∗12 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
v∗13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0
v∗14 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
v∗15 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0
v∗16 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
v∗17 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
v∗18 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1
v∗19 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
v∗20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
v∗21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0
v∗22 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 1
v∗23 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0
v∗24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
v∗25 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1
v∗26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1
v∗27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0
v∗28 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
v∗29 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0
v∗30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0
v∗31 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0
v∗32 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
v∗33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
v∗34 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0
v∗35 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
v∗36 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0
v∗37 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0

3.2. Representation of Nigeria Map in Graph

The Nigeria map, including all the states and Federal Terri-
tory Capital (F.C.T), can be represented in a graph, see Figure
9. First, let the border between states be represented by edges
and the states be vertices. The connection between the borders
(edges) and the states (vertices) is the graph obtained from the
Nigeria map.

Figure 9. The Map of Nigeria with states (and F.C.T).

Now, let Abia −v∗1, Adamawa −v
∗
2, Akwa Ibom −v

∗
3,

Anambra −v∗4, Bauchi −v
∗
5, Bayelsa −v

∗
6, Benue −v

∗
7,

Borno −v∗8, Cross River −v
∗
9, Delta −v

∗
10, Ebonyi

−v∗11, Edo −v
∗
12, Ekiti −v

∗
13, Enugu −v

∗
14, Gombe

−v∗15, Imo −v
∗
16, Jigawa −v

∗
17, Kaduna −v

∗
18, Kano

−v∗19, Katsina −v
∗
20, Kebbi −v

∗
21, Kogi −v

∗
22, Kwara

−v∗23, Lagos −v
∗
24, Nasarawa−v

∗
25, Niger −v

∗
26, Ogun

−v∗27, Ondo −v
∗
28, Osun −v

∗
29, Oyo −v

∗
30, Plateau −v

∗
31,

Rivers −v∗32, Sokoto −v
∗
33, Taraba −v

∗
34, Yobe −v

∗
35,

Zamafara −v∗36 and F.C.T −v
∗
37.

Thus, the representation of vertices and edges gives the adja-
cency matrix of the states (and F.C.T) in Nigeria, see Table 2.
Using the Sage and Graphviz packages, the representation of
Table 2 in Voronoi diagram and dual graphs are given in Figure
10, 11 and 12 respectively.

3.3. Results and Discussions

The followings are the results and useful analysis obtained from
Figure 12. There is no presence of a loop since no state can
share a border with herself. Lagos (v∗24) is a pendant because it
borders almost entirely the ocean and is suitable for a seaport.
The colour number indicated on the vertices is the chromatic
number. Thus, the chromatic number χ(G) (the minimum num-
ber of colours required for colouring the regions of a graph) is
4. Readers are advised to colour the Nigeria map with 4 colours
such that no two states (vertices) with the same colour share a
border (edge).

The largest number of neighbors of a vertex in the graph, the
maximum degree, is 11 which corresponds to v∗22. That means
Kogi state (v∗22) shares a border with 11 other states, which
makes it a commercial and geographical state of Nigeria. For
the commercial purpose, Amazon (Cadabra Inc) can establish a
warehouse in Kogi state to minimize the cost of transportation.

5



Babarinsa / J. Nig. Soc. Phys. Sci. 4 (2022) 844 6

Figure 10. The Voronoi diagram of Nigeria map.

Figure 11. The dual graph of Nigeria map.

Using Kogi state as a reference, the other warehouses can be
situated in Kaduna state (v∗18), Ogun state (v

∗
27), Abia state (v

∗
1)

and Gombe state
(
v∗15
)

which will not only cover five geopolit-
ical zone of the country but also saves the company the cost to
build minimum number of warehouses require to serve Nigeria
and neighbouring countries. These strategic states will serve
other neigbouring countries, except Kogi state, if the needs
arise. For instance, Ogun state warehouse can directly serve
Benin Republic, Kaduna state can serve part of Niger Republic,
Abia state serves part of Cameroon, and Gombe state can serve
both Chad Republic and part of Cameroon.

Figure 12. The graph of Nigeria map.

The connected component of the graph is 1. The weight of
the Minimum Spanning Tree (MST) is 36. The graph radius
(minimum eccentricity of any vertex in the graph) and graph
diameter (maximum eccentricity) from the figure are 4 (v∗7 ⇒
v∗22 ⇒ v

∗
28 ⇒ v

∗
27 ⇒ v

∗
24 ) and 7 ( v

∗
8 ⇒ v

∗
2 ⇒ v

∗
34 ⇒ v

∗
7 ⇒ v

∗
22 ⇒

v∗28 ⇒ v
∗
27 ⇒ v

∗
24 ) respectively.

Figure 12 has no Euler circuit (simple circuit contain-
ing every edge) because there are more than two states(
v∗2,v

∗
3,v
∗
8,v
∗
16,v

∗
21 and v

∗
30) bordering exactly three states, or

two states
(
v∗14,v

∗
23,v

∗
29 and v

∗
36 ) bordering exactly five states.

This implies Euler circuit cannot exist since the number of odd
degrees is higher than two. The Hamiltonian path from the
dual graph indicates that a Nigerian who is willing to visit all
states without traversing any state twice can do so by follow-
ing these paths: v∗1 ⇒ v

∗
3 ⇒ v

∗
9 ⇒ v

∗
7 ⇒ v

∗
11 ⇒ v

∗
14 ⇒ v

∗
4 ⇒

v∗16 ⇒ v
∗
32 ⇒ v

∗
6 ⇒ v

∗
10 ⇒ v

∗
12 ⇒ v

∗
22 ⇒ v

∗
25 ⇒ v

∗
37 ⇒ v

∗
18 ⇒ v

∗
5 ⇒

v∗31 ⇒ v
∗
34 ⇒ v

∗
2 ⇒ v

∗
8 ⇒ v

∗
15 ⇒ v

∗
35 ⇒ v

∗
17 ⇒ v

∗
19 ⇒ v

∗
20 ⇒ v

∗
36 ⇒

v∗33 ⇒ v
∗
21 ⇒ v

∗
26 ⇒ v

∗
23 ⇒ v

∗
13 ⇒ v

∗
28 ⇒ v

∗
29 ⇒ v

∗
30 ⇒ v

∗
27 ⇒ v

∗
24.

From Table 2, the determinant of the adjacency matrix is −6822
(clockwise orientation) and the spectrum of the adjacency ma-
trix are
λ
∗
1 =−3.0149, λ

∗
2 =−2.5616, λ

∗
3 =−2.3765, λ

∗
4 =−2.3457,

λ
∗
5 =−2.1655, λ

∗
6 =−2.1054, λ

∗
7 =−2.0253, λ

∗
8 =−1.9140,

λ
∗
9 = −1.7695, λ

∗
10 = −1.7151, λ

∗
11 = −1.5978, λ

∗
12 =

−1.4870,
λ
∗
13 = −1.3401, λ

∗
14 = −1.3257, λ

∗
15 = −1.2377, λ

∗
16 =

−1.1903,
λ
∗
17 = −0.7940, λ

∗
18 = −0.6964, λ

∗
19 = −0.5332, λ

∗
20 =

−0.3504,
λ
∗
21 =−0.2638, λ

∗
22 = 0.0641, λ

∗
23 = 0.1458, λ

∗
24 = 0.2270,

λ
∗
25 = 0.6558, λ

∗
26 = 0.6833, λ

∗
27 = 0.9538, λ

∗
28 = 1.0645,

λ
∗
29 = 1.4782, λ

∗
30 = 1.8905, λ

∗
31 = 2.2471, λ

∗
32 = 2.6553,

λ
∗
33 = 3.0397, λ

∗
34 = 3.3508, λ

∗
35 = 4.0026, λ

∗
36 = 4.7088,

λ
∗
37 = 5.6430. Thus, the energy of the graph is E(G) = 65.6201,

6



Babarinsa / J. Nig. Soc. Phys. Sci. 4 (2022) 844 7

which is non-hypoenergetic.
To compute the Laplacian energy (see Equation 5) from Ta-

ble 2, we evaluate the degree matrix via Equation 4. Then its
spectrum are
µ
∗
1 = 0.0000, µ

∗
2 = 0.2841, µ

∗
3 = 0.4619, µ

∗
4 = 0.6405,

µ
∗
5 = 1.0892, µ

∗
6 = 1.3870, µ

∗
7 = 1.4319, µ

∗
8 = 1.9546,

µ
∗
9 = 2.3059, µ

∗
10 = 2.5968, µ

∗
11 = 2.8290, µ

∗
12 = 2.9777,

µ
∗
13 = 3.2076, µ

∗
14 = 3.3923, µ

∗
15 = 3.5828, µ

∗
16 = 4.0672,

µ
∗
17 = 4.1943, µ

∗
18 = 4.5491, µ

∗
19 = 4.5880, µ

∗
20 = 5.0092,

µ
∗
21 = 5.1446, µ

∗
22 = 5.4446, µ

∗
23 = 5.6693, µ

∗
24 = 5.8715,

µ
∗
25 = 5.9542, µ

∗
26 = 5.9889, µ

∗
27 = 6.1590, µ

∗
28 = 6.7064,

µ
∗
29 = 7.2008, µ

∗
30 = 7.4258, µ

∗
31 = 7.4721, µ

∗
32 = 7.6544,

µ
∗
33 = 8.0111, µ

∗
34 = 8.3096, µ

∗
35 = 8.6034, µ

∗
36 = 9.5428,

µ
∗
37 = 12.2923 and its Laplacian energy is LE(G) = 87.6227.

The energies of this graph could be used by the security agen-
cies (such as NIA, DIA and DSS) to counter terrorism in Nige-
ria, since the country has (land and coastline) border of about
19,382km with 1400 illegal entry points.

4. Conclusion

The retrogressive development in Nigeria is shown by the
paucity of application of graph theory. The dual graph of the
Nigeria map shows the connectivity between states which can
be used as a transportation heuristic for road, water, and rail
systems. Further research implementations and applications of
graph theory to the ministries, agencies, or sectors in Nigeria
will be important for the country to be the giant of Africa.

Acknowledgments

The author thanks the anonymous referees for positive sug-
gestions in improving this paper.

References

[1] G. Chartrand, P. Zhang, A first course in graph theory, Courier Corpora-
tion, 2013.

[2] K. H. Rosen, K. Krithivasan, Discrete mathematics and its applications,
McGraw-Hill Education, Singapore, 2015.

[3] F. Harary, A seminar on graph theory, Courier Dover Publications, 2015.
[4] H. Sachs, M. Stiebitz, R. J. Wilson, An historical note: Euler’s

königsberg letters, Journal of Graph Theory 12 (1988) 133.
doi:https://doi.org/10.1002/jgt.3190120114.

[5] S. M. Cioabă, A first course in graph theory and combinatorics, Vol. 55,
Springer, 2009.

[6] J. A. Bondy, U. S. R. Murty, et al., Graph theory with applications, Vol.
290, Macmillan London, 1976.

[7] D. B. West, et al., Introduction to graph theory, Vol. 2, Prentice Hall,
2001.

[8] A. E. Brouwer, W. H. Haemers, Spectra of graphs, Springer Science &
Business Media, 2011.

[9] S. Shirinivas, S. Vetrivel, N. Elango, Applications of graph theory in com-
puter science an overview, International journal of engineering science
and technology 2 (2010) 4610.

[10] N. Trinajstic, Chemical graphs, in: Chemical graph theory, pp. 45–60.
doi:https://doi.org/10.1201/9781315139111.

[11] R. Bapat, D. Kalita, S. Pati, On weighted directed graphs,
Linear Algebra and its Applications 436 (2012) 99.
doi:https://doi.org/10.1016/j.laa.2011.06.035.

[12] K. Guo, B. Mohar, Hermitian adjacency matrix of digraphs and
mixed graphs, Journal of Graph Theory 85 (2015) 217.
doi:https://doi.org/10.1002/jgt.22057.

[13] S. Arumugam, A. Brandstädt, T. Nishizeki, K. Thulasiraman, Handbook
of graph theory, combinatorial optimization, and algorithms, Chapman
and Hall/CRC, 2016.

[14] A. Bickle, Fundamentals of Graph Theory, Vol. 43, American Mathemat-
ical Soc., 2020.

[15] O. Babarinsa, H. Kamarulhaili, Mixed energy of a mixed hourglass graph,
Communications in Mathematics and Applications 10 (2019) 45.
doi:https://doi.org/10.26713/cma.v10i1.1143.

[16] O. Babarinsa, H. Kamarulhaili, Mixed hourglass graph, in: AIP Con-
ference Proceedings, Vol. 2184, AIP Publishing LLC, 2019, p. 020003.
doi:https://doi.org/10.1063/1.5136357.

[17] J. L. Gross, J. Yellen, M. Anderson, Graph theory and its applications,
Chapman and Hall/CRC, 2018.

[18] J. M. Harris, J. L. Hirst, M. J. Mossinghoff, Combinatorics and graph
theory, Vol. 2, Springer, 2008.

[19] I. Gutman, Chemical Graph Theory: The Mathematical
Connection, Vol. 51, Academic Press, 2006, pp. 125–138.
doi:https://doi.org/10.1016/S0065-3276(06)51003-2.

[20] V. Nikiforov, The energy of graphs and matrices, Journal of Math-
ematical Analysis and Applications 326 (2007) 1472. doi:https:/
/doi.org/10.1016/j.jmaa.2006.03.072.

[21] I. Gutman, Hyperenergetic and hypoenergetic graphs, Selected Topics on
Applications of Graph Spectra, Math. Inst., Belgrade (2011) 113–135.

[22] O. Babarinsa, H. Kamarulhaili, On determinant of laplacian matrix and
signless laplacian matrix of a simple graph, in: International Conference
on Theoretical Computer Science and Discrete Mathematics, Vol. 10398,
Springer, 2017, pp. 212–217.

[23] D. Kiani, M. Mirzakhah, On the laplacian characteristic polynomials of
mixed graphs, Electronic Journal of Linear Algebra 30 (2015) 135.
doi:https://doi.org/10.13001/1081-3810.2959.

[24] S. Majstorovic, A. Klobucar, I. Gutman, Selected topics from the theory
of graph energy: hypoenergetic graphs, Applications of Graph Spectra,
Math. Inst., Belgrade (2009) 65–105.

[25] Z. Huigang, B. Xiao, Z. Huaxin, Z. Huijie, Z. Jun, C. Jian, L. Hanqing,
Hierarchical remote sensing image analysis via graph laplacian energy,
IEEE Geoscience and Remote Sensing Letters 10 (2012) 396.

[26] E. S. LENI, et al., A technique for classification of high resolution satel-
lite images using object-based segmentation., Journal of Theoretical &
Applied Information Technology 68 (2014) 275.

[27] I. Gutman, B. Furtula, Graph energies and their applications, Bul-
letin (Académie serbe des sciences et des arts. Classe des sciences
mathématiques et naturelles. Sciences mathématiques) 44 (2019) 29

[28] I. Gutman, H. Ramane, Research on graph energies in 2019, MATCH
Commun. Math. Comput. Chem 84 (2020) 277.

7