INTERNATIONAL JOURNAL OF RESEARCH AND SCIENTIFIC INNOVATION (IJRSI)
ISSN No. 2321-2705 | DOI: 10.51244/IJRSI |Volume XII Issue IX September 2025
Page 3374
www.rsisinternational.org
Graph Theory as a Framework for Enhancing the Mathematical
Learning Process
Nor Kamariah Kasmin
1,*
, Tahir Ahmad
2
1
Faculty of Computer and Mathematical Sciences, University Technology Mara, Johor Branch, Pasir
Gudang Campus, 81750 Masai, Johor, Malaysia.
2
Fellow of Malaysian Mathematical Sciences Society, Malaysian Mathematical Sciences Society, 43600
Bangi, University Kebangsaan Malaysia, Selangor, Malaysia.
DOI: https://doi.org/10.51244/IJRSI.2025.120800305
Received: 04 Sep 2025; Accepted: 10 Sep 2025; Published: 08 October 2025
ABSTRACT
Graph theory is one of the important strands in mathematics and serves as an interesting subject matter that
can be used as a tool for enhancing students’ mathematical learning. In the Malaysian context, the emphasis
on education is aligned with the Sustainable Development Goals (SDG 4: Quality Education), which
highlights the need to develop students who are not only competent in content knowledge but also able to
apply their learning meaningfully. In this paper, we propose that Graph Theory can be integrated into the
teaching and learning of mathematics as a suitable context to address the five learning standards emphasized
in Malaysia, namely problem solving, communication, reasoning, connection, and representation. Especially,
Graph Theory can play a significant role in strengthening STEM education by providing students with
opportunities to engage in critical thinking, establish meaningful links between mathematics and other
disciplines, communicate their ideas effectively, and represent mathematical concepts in ways that relate to
real-world and physical situations, thereby fostering holistic and sustainable educational development.
Keywords- graph theory, mathematical modelling, critical thinking, STEM education.
INTRODUCTION
Graph theory is one of the important branches of mathematics and serves as an interesting subject matter that
can be used as a tool for enhancing students’ mathematical learning. In the Malaysian context, the emphasis
on education is aligned with Sustainable Development Goal 4: Quality Education, which stresses the
importance of producing learners who can apply knowledge meaningfully through five key standards:
problem solving, communication, reasoning, connection, and representation [5]. Graph theory, with its strong
potential for mathematical modeling, offers opportunities to link mathematics with real-world applications
such as transport systems, biological networks, and social interactions [6]. Its integration in STEM education
can strengthen students’ ability to think critically, analyze problems, and represent mathematical concepts in
varied forms, thereby supporting inquiry-based and interdisciplinary learning [3]. Recent research highlights
that graph-based modeling tasks promote critical thinking and enhance conceptual understanding across
STEM domains [4], making graph theory a relevant and sustainable approach to nurture holistic, future-ready
learners in Malaysia. In this paper, we highlight that Graph Theory is particularly well suited to an
INTERNATIONAL JOURNAL OF RESEARCH AND SCIENTIFIC INNOVATION (IJRSI)
ISSN No. 2321-2705 | DOI: 10.51244/IJRSI |Volume XII Issue IX September 2025
Page 3375
www.rsisinternational.org
applications-based approach, as one of its fundamental problems involves finding the shortest path between
two points. To illustrate this, we propose two real-world problems designed for STEM undergraduate students
to be solved using Graph Theory, demonstrating its value as both a mathematical tool and an educational
strategy.
MATHEMATICAL MODELLING
Understanding what a mathematical model is forms the first step in connecting mathematics with the real
world. Behind every model lies a modeling process, which can involve six sub-processes: (a) formulating a
task that identifies characteristics of reality to be modeled, (b) selecting and idealizing relevant objects and
relations, (c) translating these into mathematics, (d) applying mathematical methods to obtain results, (e)
interpreting these results in relation to the original problem, and (f) evaluating the validity of the model by
comparing it with data or prior knowledge [1]. Importantly, this process is not always linear; it may require
moving back and forth between steps or repeating them to refine the model.
In schools, however, mathematical modeling often takes a simplified form, where problems are already pre-
structured, such as traditional word problems. In such cases, students mainly use step (c), creating a
mathematical picture, and step (d), performing calculations, without engaging fully in the interpretation and
validation phases. To move beyond this, Graph Theory offers a powerful tool for modeling that can integrate
all six steps of the process. When applied in classroom contexts, graph-based tasks encourage students to
formulate, represent, solve, and interpret real-world problems, thereby experiencing the complete cycle of
mathematical modeling in an accessible way as shown in Fig. 1 below.
Fig. 1 Framework of the Mathematical Modeling
GRAPH THEORY
In this section, we recall the concepts necessary to understand and supposed to be known by the students. A
nondirected graph G = (V, E) is a finite nonempty set of elements called nodes together with a set of unordered
pairs of distinct nodes called edges [2]. We denote the node set of a graph G by V and the edge set by E. The
number of elements in the node set of a graph G is called the order of G, denoted n, and the number of
elements in the edge set of a graph G is called the size of G, denoted m. A pair of nodes v
i
and v
j
in V are
adjacent if they are connected by an edge; otherwise, v
i
and v
j
are nonadjacent. The degree of v, denoted
deg(v), is the number of nodes adjacent to v. Note that a node of degree zero is called an isolated node. The
minimum degree of G, denoted δ(G), is the minimum degree among the nodes of G and the maximum degree
of G, denoted Δ(G), is the maximum degree among the nodes of G. A node u is said to be connected to a node
INTERNATIONAL JOURNAL OF RESEARCH AND SCIENTIFIC INNOVATION (IJRSI)
ISSN No. 2321-2705 | DOI: 10.51244/IJRSI |Volume XII Issue IX September 2025
Page 3376
www.rsisinternational.org
v in a graph G if there exists a sequence of edges from u to v in G. A graph G is connected if every two of its
nodes are connected.
In this unit we will also examine a concept in Graph Theory called vertex coloring. This concept can be very
useful in real life applications, such as how to manage conflicts of interest. For example, we will later see how
graph coloring techniques can be applied to assigning frequencies to radio stations, scheduling club meetings,
and coloring the countries of a map. By a coloring of a graph G, we mean the assignment of colors (numbers)
to the vertices of G, one color to each vertex, so that adjacent vertices are assigned different colors. A k-
coloring of G is a coloring of G using k colors. For example, Fig. 2 shows a 5-coloring of the graph G1, as
well as a 4-coloring of the graph G2.
Fig. 2 Examples of Vertex Coloring
IMPLEMENTATION VIA GRAPH THEORY
In this section, we propose a couple of problems that serve as an introduction to graphs.
Application 1. A club scheduling conflict occurs at a school in Malaysia because some students are members
of more than one club. Since clubs that share members cannot meet on the same day, the problem is to
determine the minimum number of days required in Table 1 so that no two overlapping clubs hold meetings
simultaneously.
Table 1 Clubs And Members
Clubs
Students in Multi-Clubs
Cyber Kids Club
Dayana, Helmi, Kerol
Young Entrepreneurs Club
Kerol, Dayana, Taliqah
Recreation and Adventure Club
Helmi
Robotic Club
Kerol, Raysa, Taliqah
Innovation and Invention Club
Raysa, Helmi
Crime Prevention Club
Helmi
INTERNATIONAL JOURNAL OF RESEARCH AND SCIENTIFIC INNOVATION (IJRSI)
ISSN No. 2321-2705 | DOI: 10.51244/IJRSI |Volume XII Issue IX September 2025
Page 3377
www.rsisinternational.org
Solution
In accordance with the process of mathematical modeling, the real-world context is translated into a graph-
theoretic representation shown in Fig. 3. Each vertex in the graph corresponds to a specific club, and an edge
is established between two vertices if the associated clubs share at least one common member. For example,
the Cyber Kids Club (CK) is adjacent to the Young Entrepreneurs Club (YE) because both Dayana and Kerol
hold memberships in these clubs. Accordingly, the model can be formalized with the following vertex set: CK
– Cyber Kids Club, YE – Young Entrepreneurs Club, RA – Recreation and Adventure Club, RC – Robotic
Club, II – Innovation and Invention Club, and CP – Crime Prevention Club.
Fig. 3 A Graph Representation for Clubs and Members
The next step involves applying a graph coloring approach, where the objective is to minimize the number of
colors used in assigning labels to the vertices. Specifically, each vertex is assigned a color such that no two
adjacent vertices share the same color. In this context, the colors are interpreted as days of the week, with Day
1 corresponding to Color 1, Day 2 to Color 2, and so forth. It is shown in Fig. 4.
Fig. 4 A Vertex Coloring for a Club Scheduling
The resulting graph requires four distinct colors for a proper coloring. Interpreted within the real-world
context, this indicates that a minimum of four days is necessary to schedule weekly meetings such that no
student is required to attend two clubs on the same day. This lower bound arises due to Helmi’s participation in
multiple clubs, which constrains the scheduling and ensures that four days is the minimal feasible solution. The
corresponding schedule is summarized in the Table 2 below for clarity.
Table 2 Club Scheduling By Days
Day 1
Day 2
Day 3
Day 4
Cyber Kids Club
Young Entrepreneurs
Club
Crime Prevention Club
Recreation and
Adventure Club
Robotic Club
Innovation and
Invention Club
INTERNATIONAL JOURNAL OF RESEARCH AND SCIENTIFIC INNOVATION (IJRSI)
ISSN No. 2321-2705 | DOI: 10.51244/IJRSI |Volume XII Issue IX September 2025
Page 3378
www.rsisinternational.org
Application 2. A radio station conflict where frequencies would interfere with each other if the stations were
too close. The Malaysian Communications and Multimedia Commission (MCMC) ensures that broadcasts
from one radio station do not interfere with broadcasts from other stations. This is done by assigning an
appropriate frequency to each station. MCMC requires that stations within transmitting range of each other
must use different frequencies. Suppose that MCMC enforces a new rule where stations located within 500
kilometers of each other must be assigned different frequencies. The locations of seven stations are given in
the grid below, with the distances between the stations in kilometers. MCMC wants you to assign a frequency
to each station so that no two stations interfere with each other, while also using the fewest possible number of
frequencies.
Solution
Following the process of mathematical modeling, we begin with a real-world scenario and translate the given
grid into a graph-theoretic representation as shown in Fig. 5. In this model, each vertex corresponds to a radio
station, and an edge is established between two vertices if the distance between the corresponding stations is
less than or equal to 500 miles. Consequently, the frequency assignment problem reduces to analyzing the
adjacency relations among these vertices, since stations located within 500 miles must be allocated distinct
frequencies.
Fig. 5 A Graph Representation for Seven Radio Stations.
The objective is to determine a vertex coloring of the graph using the minimum possible number of colors,
such that no two adjacent vertices share the same color. In this context, each color represents a distinct radio
frequency assigned to the corresponding station as shown in Fig. 6.
INTERNATIONAL JOURNAL OF RESEARCH AND SCIENTIFIC INNOVATION (IJRSI)
ISSN No. 2321-2705 | DOI: 10.51244/IJRSI |Volume XII Issue IX September 2025
Page 3379
www.rsisinternational.org
Fig. 6 A Vertex Coloring for the Corresponding Radio Stations.
The resulting graph requires three distinct colors for a proper coloring. Interpreted in the context of the real-
world problem, this indicates that a minimum of three radio frequencies is necessary to ensure that any two
stations located within 500 miles of each other are assigned different frequencies.
Application 3. A map-coloring problem arises when two countries that share a common border must be
assigned different colors. In practice, this principle is frequently applied in cartography, where maps are
designed such that adjacent countries are distinguished by distinct colors to enhance clarity and prevent visual
blending. For example, consider the case of a map of Peninsular Malaysia in Fig. 7 provided by a mapmaker,
where the objective is to assign colors to each country in accordance with this adjacency constraint.
Fig. 7 Peninsular Malaysia Map.
In this given real-world situation we can represent our problem with a graph model. Let each country be a
vertex where vertices are adjacent if they share a border in Fig 8.
Fig. 8 A Graph Presentation for Peninsular Malaysia Map.
By applying vertex coloring, we can see that four colors are needed to color this map as shown in Fig. 9.
INTERNATIONAL JOURNAL OF RESEARCH AND SCIENTIFIC INNOVATION (IJRSI)
ISSN No. 2321-2705 | DOI: 10.51244/IJRSI |Volume XII Issue IX September 2025
Page 3380
www.rsisinternational.org
Fig. 9 Adjacent countries are distinguished by distinct colors.
CONCLUSION
This study has demonstrated the applicability of graph theory as a powerful mathematical tool in addressing
real-world problems through the use of vertex coloring across three different situations. By translating real-life
contexts into mathematical representations, students are not only able to simplify complex data but also to
approach problem-solving in a structured and logical manner. The results highlight how graph theory can be
effectively implemented in STEM education, particularly in cultivating essential competencies such as data
analysis, mathematical modeling, and critical thinking. These competencies align directly with the five key
learning standards which are problem solving, communication, reasoning, connection, and representation.
They outlined in modern mathematics education frameworks and emphasized in Malaysia’s commitment to the
Sustainable Development Goals (SDG 4: Quality Education). Furthermore, the integration of graph theory
provides students with the opportunity to connect abstract mathematics with practical applications, reinforcing
interdisciplinary learning in STEM fields. Ultimately, this research underscores that embedding graph theory
into teaching practices not only enriches mathematical understanding but also nurtures higher-order thinking
skills, thereby preparing students to navigate complex challenges in both academic and real-world settings.
ACKNOWLEDGMENT
The authors would like to express their sincere gratitude to Universiti Teknologi Mara (UiTM) Johor Branch,
Pasir Gudang Campus for providing the resources and support necessary to conduct this research.
REFERENCES
1. Blomhøj, M., & Jensen, T. H. (2003). Developing mathematical modeling competence: Conceptual
clarification and educational planning. Teaching Mathematics and its Applications, 22(3), 123–139.
2. Chartrand, G., Lesniak, L., & Zhang, P. (2010). Graphs & Digraphs (5th ed.). Boca Raton, FL:
Chapman and Hall/CRC.
3. Ismail, N., Arshad, M., & Abas, H. (2022). Computational thinking in STEM education: A Malaysian
perspective. Journal of Education and Information Technologies, 27(5), 6547–6563.
https://doi.org/10.1007/s10639-022-10914-3.
4. Li, X., & Gao, Y. (2021). Graph-based mathematical modeling and its role in STEM education.
Mathematics, 9(23), 3110. https://doi.org/10.3390/math9233110.
5. Scitepress. (2018). Mathematical processes in K-12 curriculum. In Proceedings of the 10th
International Conference on Education and New Learning Technologies. Retrieved from
https://www.scitepress.org/Papers/2018/99142/pdf/index.html.
6. Wikipedia. (2023). Graph theory. In Wikipedia. Retrieved from
https://en.wikipedia.org/wiki/Graph_theory.
