ASSIGNMENT 1 FRONT SHEET

Qualification Pearson BTEC Level 5 Higher National Diploma in Computing

Unit number and title Unit 18: Discrete Maths

Submission date 28/2/2024 Date Received 1st submission

Resubmission Date 6/3/2024 Date Received 2nd submission

Student Name TRAN LE DUY Student ID BH00460

Class IT0601 Assessor name Tạ Quang Hiếu

Student declaration
I certify that the assignment submission is entirely my own work and I fully understand the consequences of plagiarism. I understand that
making a false declaration is a form of malpractice.

Student’s signature DUY

Grading grid

P1 P2 P3 P4 M1 M2 D1 D2
❒ Summative Feedback: ❒ Resubmission Feedback:

Grade: Assessor Signature: Date:

Internal Verifier’s Comments:

Signature & Date:

Contents
Activity 1 .....................................................................................................................................................................................4
Determine the cardinalities of two sets, three sets. ..............................................................................................4
Prime factorization for each number provided, then list the factors as bags, and determine the
cardinalities of bags. ..........................................................................................................................................................7
Identify the inverse function of a given function. ...................................................................................................9
Prove a given equality of sets using membership tables and using the subset property. ................... 12
Activity 2 .................................................................................................................................................................................. 13
Discuss two notable instances of binary trees, providing both quantitative and qualitative
analyses. You should contain two contents as follows:..................................................................................... 13
What is a binary tree? ................................................................................................................................................ 13
Provides some common types of binary trees such as complete binary trees, complete binary
trees, balanced binary trees,… ................................................................................................................................ 14
State Dijkstra’s Algorithm in an undirected graph and then apply to determine the shortest path
length between the two vertices in specific a case. ............................................................................................ 20
1.State Dijkstra’s Algorithm in an undirected graph ..................................................................................... 20
2. Apply Dijkstra’s algorithm to determine the shortest path length between vertices A and Z in
the provided weighted graph.................................................................................................................................. 21
Assess whether a Eulerian and Hamiltonian circuit exists in an undirected graph. ........................... 28
Reference ................................................................................................................................................................................. 30
Activity 1
Determine the cardinalities of two sets, three sets.

1. Let A and B be two non-empty finite sets. Assume that cardinalities of the sets A , B and A ∩ B
are ̅9b
̅̅̅ , ̅̅̅
2a a and , a + b respectively. Determine the cardinality of the set A ∪ B

From the above question, based on my ID number, we have the following information:
| A | = 96
| B | = 24
| A ∩ B | = 10
Now , using the inclusionexclusion principle :
|A ∪ B| = | A | + | B | - |A ∩ B |
 |A ∪ B| = 96 + 24 – 10
 |A ∪ B| = 110
So the cardinality of the set A ∪ B equals 110

3a , |A ∪ B| = ̅̅̅̅̅
2. We have |A – B| = ̅̅̅ 11𝑏 and |A ∩ B| = ̅1𝑎
̅̅̅ . Determine | B | .

From the above question, based on my ID number, we have the following information
|A – B| = 34
|A ∪ B| = 116
|A ∩ B| = 14
Now , using the inclusionexclusion principle :
|A ∪ B| = | A | + | B | - |A ∩ B|
 116 = | A | + | B | - 14
So , we have | A | + | B | = 130
To find | A| and | B| , we need to leverage additional information provided, namely | A – B | . I've
constructed a relationship table for | A | , | B | , | A – B | , | A ∩ B | , and | A - (A ∩ B) | to facilitate the
discovery of their interconnections.

From the table provided, we can observe that the sets of elements for A - B and A - (A ∩ B) are
identical, so we can deduce:
| A – B | = |A | - |A ∩ B|
 34 = |A | - 14
So , we have | A | = 48
We also have | A | + | B | = 130
From the two points above, we can infer :
| B | = 130 - 48
We have reasoned and found out that | B | equals 82.
̅̅̅̅̅ customers. Suppose ̅̅̅̅̅
3. At a local market, there are 35b ̅̅̅̅ have
11a have purchased fruits, 9b
purchased vegetables, ̅̅̅8a have purchased bakery items, ̅4b
̅̅̅ have purchased both fruits and
vegetables, ̅3b
̅̅̅ have purchased both vegetables and bakery items, ̅̅̅
2a have purchased both fruits
̅̅̅
and bakery items, and 1a have purchased all three categories. How many customers have not
purchased anything?

Based on what has been given and my ID number, we can represent the information as follows:
( |A| = 114 ) (customers who purchased fruits)
( |B| = 96 ) (customers who purchased vegetables)
( |C| = 84 ) (customers who purchased bakery items)
( |A ∩ B| = 46 ) (customers who purchased both fruits and vegetables)
( |B ∩ C| = 36 ) (customers who purchased both vegetables and bakery items)
( |A ∩ C| = 24 ) (customers who purchased both fruits and bakery items)
( |A ∩ B ∩ C| = 14 ) (customers who purchased all three categories)
To determine the number of customers who did not buy anything, we first need to determine the
total number of customers who bought at least one of the goods, whether fruits, vegetables or bread.
Or performed as
|A ∪ B ∪ C|
Now, using the inclusion exclusion principle:

|A ∪ B ∪ C| = |A| + |B| + |C|- |A ∩ B| - |B ∩ C| - |A ∩ C| + |A ∩ B ∩ C|

<=> |A ∪ B ∪ C| = 114 + 96+ 84 – 46 – 36 – 24 + 14 = 202

Now, to find the number of customers who have not purchased anything, subtract this from the total
number of customers (35b):

Customers not purchasing anything = 35b - |A ∪ B ∪ C| = 356 - 202 = 154

So, there are 154 customers who have not purchased anything.
Prime factorization for each number provided, then list the factors as bags,
and determine the cardinalities of bags.

Based on what has been given and my ID number, we can represent the information as follows:
1) List the bag of prime factor for each 142, 260
a) We define A as the bag of prime factors of 142.
According to the definition of prime factor 142 can be expressed as 2 𝑥 71
Therefore A = {|2:1, 71:1|}
This means that the bag of prime factors of 142 is represented by {|2:1, 71:1|}.
b) We define B as the bag of prime factors of 260.
According to the prime factorization, 260 can be expressed as 22 𝑥 5 𝑥 13
Therefore, B = {|2:2,5:1,13:1|}.
This means that the bag of prime factors of 260 is represented by {|2:2,5:1,13:1|}.
2) Based on the information provided earlier:
We define A as the bag of prime factors of 142, and B as the bag of prime factors of 260.
The prime factorization of 142 is {|2:1,71:1|}
The prime factorization of 260 is {|2:2,5:1,13:1|}.
a) We need to calculate the cardinalities of bags A and B, represented as |A| and |B|, respectively.
Given that:
|A| = 1+1 = 2
(2 is the sum of the exponents in the prime factorization of 142)
|B| = 2 + 1 + 1 = 4
(4 is the sum of the exponents in the prime factorization of 260)
The correct cardinalities are:
|A| = 2
|B| = 4
Therefore, the cardinality of the bag of prime factors for 142 is 2, and for 260, it is 4.
b) We need to calculate the cardinality of the intersection of bags A and B, represented as |A ∩ B|. To
find |A ∩ B|, we first determine A ∩ B using the Intersections of Bags concept.
We have A ∩ B = {|2:1|}
Therefore : |A ∩ B| = 1
So, the cardinality of the intersection of the bag of prime factors for 142 and 260 is 1.
c) We need to calculate the cardinality of the union of bags A and B, represented as |A ∪ B|. To find
|A ∪ B|, we first determine A ∪ B using the Union of Bags concept.

We have A ∪ B = {|2:2,5:1,13:1,71:1|}
Therefore : |A ∪ B| = 2+1+1+1 = 5
So, the cardinality of the union of the bag of prime factors for 142 and 260 is 5.
d) We need to calculate the cardinality of the differemce of bags A and B, represented as |A – B| and
|B – A| . To find |A – B| and |B – A| ,we first determine A - B using the Diference of Bags concept.
The expression A - B represents the elements in bag A with adjusted multiplicities based on the
difference in multiplicities between A and B, and B - A similarly represents the elements in bag B
with adjusted multiplicities based on the difference in multiplicities between B and A.
We have A - B = {|71:1,|}
Therefore : |A - B| = 1
We have B - A = {|2:1,5:1,13:1|}
Therefore : |B - A| = 3
So, the cardinality of the difference of the bag of prime factors for 142 and 260 when considering
multiplicities, results in a cardinality of 1 for elements unique to A and 3 for elements unique to B.

Identify the inverse function of a given function.

1)
a)we have f : R->R with f(x) = 6x+4
Assume that f(x1 ) = f(x2 ), where x1 , x2 ∈ R. Then,
6x1 +4 = 6x2 + 4
Therefore, 6x1 = 6x2 which implies
x1 = x2
Hence, the function f is one-to-one
𝑦−4
Let y be any element of the codomain R. Choose x = . It is easy to see that the real numbers are
6
closed under subtraction and non-zero division, i.e., x ∈ R. Also,
𝑦−4 𝑦−4
f(x) = f ( ) = 6( ) +4=y
6 6

Therefore, we found an x ∈ R such that f(x) = y. In other words, given an arbitrary element of the
codomain, we have shown a preimage in the domain.
We conclude that f is onto.
The function f is both one-to-one and onto. Hence, f is a one-to-one correspondence
The function f has an inverse because it is a one-to-one correspondence.
To reverse the correspondence, suppose that y is the image of x, so that
y = 6x+4
which implies
𝑦−4
x= 6
𝑦−4
This means that is the unique element of R that is sent to y by f.
6
𝑦−4
Consequently, f −1 (y) = where y ∈ R
6

b) we have f : [-6,+∞) ->[0,+∞) with f(x) = √x + 6

Assume that f(x1 ) = f(x2 ), where x1 , x2 ∈ R. Then,

√x1 + 6 = √x2 + 6

Therefore, x1 + 6= x2 + 6 which implies

x1 = x2
Hence, the function f is one-to-one
Let y be any element of the codomain [0,+∞). Choose x = 𝑦 2 − 6 . It is easy to see that the real
numbers are closed under subtraction and non-zero division, i.e., x ∈ [-6,+∞). Also,

f(x) = f (𝑦 2 − 6) = √𝑦 2 − 6 + 6 = y

Therefore, we found an x ∈ [-6,+∞) such that f(x) = y. In other words, given an arbitrary element of
the codomain, we have shown a preimage in the domain.
We conclude that f is onto.
The function f is both one-to-one and onto. Hence, f is a bijection, and this implies it is invertible.
The function f has an inverse because it is a one-to-one correspondence.
To reverse the correspondence, suppose that y is the image of x, so that

y = √x + 6
which implies
x = 𝑦2 − 6
This means that 𝑦 2 − 6 is the unique element of [-6,+∞) that is sent to y by f.
Consequently, f −1 (y) = 𝑦 2 − 6 where y ∈ [0,+∞)
 2x + 4 , if x < 0
2 . Base on my ID . Given that f(x) = { and g(x) = 6x -4
x 3 + 6 , if x ≥ 0
To find the composition g o f , we subtitute f(x) into g(x) to each value of x:
a)For x < 0, use f(x) = 2x+4:
𝑔 ∘ 𝑓 = g(f(x)) = g(2x+4) = 6(2x+4) - 4 = 12x+24-4 = 12x+20 , if x < 0
b)For x >= 0 , use f(x) = x 3 + 6:
𝑔 ∘ 𝑓 = g(f(x)) = g(x 3 + 6) = 6(x 3 + 6) – 4 = 6x 3 + 36 if x >= 0
So the expression for 𝑔 ∘ 𝑓 is :
12x + 20 , if x < 0
𝑔∘𝑓= {
6x 3 + 36 , if x >= 0
Prove a given equality of sets using membership tables and using the subset
property.

1)We will prove that the two sets A ∩ B and A ∪ B are equal by showing that each set is a subset of
the other.
1. We will show that ̅̅̅̅̅̅̅̅̅̅̅̅
A∪B∪C ⊆A ̅∩B
̅ ∩ C̅ . We do this by showing that if x is in ̅̅̅̅̅̅̅̅̅̅̅̅
A ∪ B ∪ C , then it
̅∩B
must also be in A ̅ ∩ C̅. Now suppose that x ∈ ̅̅̅̅̅̅̅̅̅̅̅̅
A ∪ B ∪ C . By the definition of complement,
x∉A∪B∪C
X ∉ A or x ∉ B ∪ C
X ∉ A or x ∉ B or x ∉ C
It follows that
̅ or x ∈ B
x∈A ̅ or x ∈ C̅
̅∩B
Thus, x ∈ A ̅ ∩ C̅. We conclude that ̅̅̅̅̅̅̅̅̅̅̅̅
A∪B∪C ⊆ A ̅∩B
̅ ∩ C̅
̅∩B
. We will show that A ̅ ∩ C̅ ⊆ ̅̅̅̅̅̅̅̅̅̅̅̅ ̅∩B
A ∪ B ∪ C We do this by showing that if x is in A ̅ ∩ C̅ ,

then it must also be in ̅̅̅̅̅̅̅̅̅̅̅̅

A∪B∪C
. Now suppose that x ∈ A ̅∩B ̅ ∩ C̅ . By the definition of complement,

̅ or x ∈ B
x∈A ̅ or x ∈ C̅

x ∉ A or x ∉ B or x ∉ C
x ∉ A or x ∉ B ∪ C
x∉A∪B∪C
. x ∈ ̅̅̅̅̅̅̅̅̅̅̅̅
A∪B∪C
Therefore,
̅∩B
A ̅ ∩ C̅ ⊆ ̅̅̅̅̅̅̅̅̅̅̅̅
A∪B∪C
Because we have shown that each set is a subset of the other, the two sets are equal, and the identity
is proved
2) The membership table for these combinations of sets is shown in the table below
 A B C ̅
A ̅
B C̅ A∪B ̅̅̅̅̅̅̅̅̅̅̅̅
A∪B∪C ̅∩B
A ̅ ∩ C̅
∪C
1 1 1 0 0 0 1 0 0
0 0 0 1 1 1 0 1 1
1 1 0 0 0 1 1 0 0
1 0 1 0 1 0 1 0 0
0 0 1 1 1 0 1 0 0
0 1 1 1 0 0 1 0 0
0 1 0 1 0 1 1 0 0
1 0 0 0 1 1 1 0 0

Because the columns for ̅̅̅̅̅̅̅̅̅̅̅̅ ̅∩B

A ∪ B ∪ C and A ̅ ∩ C̅ are the same, the identity is valid.

Activity 2
Discuss two notable instances of binary trees, providing both quantitative and
qualitative analyses. You should contain two contents as follows:
What is a binary tree?
A Binary Tree Data Structure is a hierarchical data structure in which each node has at most two
children, referred to as the left child and the right child. It is commonly used in computer science for
efficient storage and retrieval of data, with various operations such as insertion, deletion, and
traversal.(Source)

A binary tree data structure can be used for a variety of purposes in computer science and
programming due to its hierarchical and organized nature. Some common applications and
functionalities of binary trees are :
Binary Search,Sorting,Expression Trees,File Systems,Decision Trees,Heap Data Structure,Huffman
Coding,Game Trees,Network Routing,Database Indexing
Provides some common types of binary trees such as complete binary trees, complete
binary trees, balanced binary trees,…
Types of Binary Tree based on the number of children:
Following are the types of Binary Tree based on the number of children:
Full Binary Tree
Degenerate Binary Tree
Skewed Binary Trees
1. Full Binary Tree
A Binary Tree is a full binary tree if every node has 0 or 2 children. The following are examples of a
full binary tree. We can also say a full binary tree is a binary tree in which all nodes except leaf
nodes have two children.
A full Binary tree is a special type of binary tree in which every parent node/internal node has
either two or no children. It is also known as a proper binary tree.

2. Degenerate (or pathological) tree

A Tree where every internal node has one child. Such trees are performance-wise same as linked
list. A degenerate or pathological tree is a tree having a single child either left or right.
3. Skewed Binary Tree
A skewed binary tree is a pathological/degenerate tree in which the tree is either dominated by the
left nodes or the right nodes. Thus, there are two types of skewed binary tree: left-skewed binary
tree and right-skewed binary tree.

Types of Binary Tree On the basis of the completion of levels:

Complete Binary Tree
Perfect Binary Tree
Balanced Binary Tree
A Binary Tree is a Complete Binary Tree if all the levels are completely filled except possibly the last
level and the last level has all keys as left as possible.
A complete binary tree is just like a full binary tree, but with two major differences:
Every level except the last level must be completely filled.
All the leaf elements must lean towards the left.
The last leaf element might not have a right sibling i.e. a complete binary tree doesn’t have to be a
full binary tree.
Complete Binary Tree
Refer to this article to read about more on Complete Tree
2. Perfect Binary Tree
A Binary tree is a Perfect Binary Tree in which all the internal nodes have two children and all leaf
nodes are at the same level.
The following are examples of Perfect Binary Trees.
A perfect binary tree is a type of binary tree in which every internal node has exactly two child
nodes and all the leaf nodes are at the same level.
Perfect Binary Tree
In a Perfect Binary Tree, the number of leaf nodes is the number of internal nodes plus 1
L = I + 1 Where L = Number of leaf nodes, I = Number of internal nodes.
A Perfect Binary Tree of height h (where the height of the binary tree is the number of edges in the
longest path from the root node to any leaf node in the tree, height of root node is 0) has 2h+1 – 1
node.
An example of a Perfect binary tree is ancestors in the family. Keep a person at root, parents as
children, parents of parents as their children.
Refer to this article to read about more on Perfect Tree
3. Balanced Binary Tree
A binary tree is balanced if the height of the tree is O(Log n) where n is the number of nodes. For
Example, the AVL tree maintains O(Log n) height by making sure that the difference between the
heights of the left and right subtrees is at most 1. Red-Black trees maintain O(Log n) height by
making sure that the number of Black nodes on every root to leaf paths is the same and that there
are no adjacent red nodes. Balanced Binary Search trees are performance-wise good as they provide
O(log n) time for search, insert and delete.
Example of Balanced and Unbalanced Binary Tree
It is a type of binary tree in which the difference between the height of the left and the right subtree
for each node is either 0 or 1. In the figure above, the root node having a value 0 is unbalanced with
a depth of 2 units.
 State Dijkstra’s Algorithm in an undirected graph and then apply to determine
the shortest path length between the two vertices in specific a case.

Base on what were given and a,b of my ID we have the weighted graph

1.State Dijkstra’s Algorithm in an undirected graph

A graph that has a number assigned to each edge is called a weighted graph.
The length of a path in a weighted graph is the sum of all weights of the edges of this path.(Source)

Given a weighted graph G with distinct vertices a, b, c, d, e, and z, the goal is to find the shortest path
from the starting vertex a to the destination vertex z using Dijkstra's algorithm. Dijkstra's algorithm
is a well-known method for solving the shortest path problem in weighted graphs. The step-by-step
breakdown of the algorithm is as follows:
1. Initialization: Set the distance from the source vertex (a) to itself as 0, and the distance to all other
vertices as infinity. Add all vertices to the priority queue.
2. Relaxation: Repeat the following steps until the priority queue is empty or the destination vertex
(z) is reached.
a. Extract the vertex with the minimum distance (u) from the priority queue.
b. For each neighboring vertex (v) of u, calculate the potential new distance from a to v through u.
c. If the newly calculated distance is shorter than the current distance to v, update the distance to
v.
d. Update the priority queue with the modified distances.
3. Result: Once the destination vertex (z) is reached or the priority queue is empty, the algorithm
terminates. The distance from a to z represents the shortest path length, and the path itself can be
reconstructed by backtracking from z to a using the stored information.
Dijkstra's algorithm guarantees the shortest path under the assumption that all edge weights are
non-negative. It efficiently explores paths in increasing order of their lengths, making it suitable for
finding single-source shortest paths in weighted graphs. .(Source)

2. Apply Dijkstra’s algorithm to determine the shortest path length between vertices A
and Z in the provided weighted graph.
Step 1 : First, the labels are now initialized so that the label of a is 0 and all other labels are ∞.
Step2 :
Next, we start at a and there are two paths including A, B of length 4 and A,C of length 4.

It follows that B and C are the closest vertex to A, and the shortest path from A to B , A to C has
length 4.
Now, we need to find the third closest vertex to A by examining all paths that begin with the
shortest path from the vertex C and B . Let’s go with C first

Now we go with B :

In this case, the third closest vertex to A is D, and the shortest path from A to D is A,C,D of length 8 .
To determine the fourth closest vertex to A, we need to checking all paths that begin with shortest
path from the vertex D

In this case, the fourth closest vertex to A is E, and the shortest path from A to E is A,C,D,E of length
9.
To determine the fifth closest vertex to A, we need to checking all paths that begin with shortest
path from the vertex E

In this case, the fifth closest vertex to a is F, and the shortest path from A to F is A,C,D,F of length 14.
It is easy to identify the sixth closest vertex to A, that is G. Here, the shortest path is A,C,D,E,G of
length 15.

Finally, to reach Z there is a unique path from G that is A,C,D,E,G,Z of length 20. It means that the
seventh closest vertex to A is Z
We conclude that the graph have shortest path between A and Z is and A,C,D,E,G,Z of length 20.
Assess whether a Eulerian and Hamiltonian circuit exists in an undirected
graph.

Vertex : 17
deg(x),deg(c),deg(e),deg(g),deg(i),deg(k),deg(l),deg(n) = 2
deg(d), deg(h),deg(y),deg(f) = 3
deg(p),deg(j),deg(q),deg(m),deg(o) = 4
So based on Conditions for Existence of Euler Paths and Circuits
A connected multigraph G has Euler circuits if and only if every vertex has even degree.
If the graph G does not have Euler circuits, then it has Euler paths if and only if it has exactly two
vertices of odd degrees.
It not a Euler Paths and Circuits

Finding Hamiltonian paths in a graph is a complex problem, and there isn't a specific set of rules
that guarantees a Hamiltonian path's existence. So First we try to use Dirac’s theorem and ore’s
theorem

Dirac's Theorem: This theorem states that if every vertex in a graph has a degree of at least n/2
(where n is the total number of vertices), then the graph is guaranteed to have a Hamiltonian cycle.
Ore's Theorem: This theorem states that if for every pair of non-adjacent vertices in a graph, the
sum of their degrees is at least n, where n is the total number of vertices, then the graph is
guaranteed to have a Hamiltonian cycle.
Let's analyze the provided graph in the context of Dirac's Theorem and Ore's Theorem to explain
why they cannot be applied to guarantee the existence of a Hamiltonian cycle:
Dirac's Theorem:
Dirac's Theorem states that if every vertex in a graph has a degree of at least n/2 (where n is the
total number of vertices), then the graph is guaranteed to have a Hamiltonian cycle.
In the provided graph:
- The total number of vertices (n) is 17.
- To satisfy Dirac's Theorem, every vertex should have a degree of at least 8.5.
However, in the graph:
deg(x),deg(c),deg(e),deg(g),deg(i),deg(k),deg(l),deg(n) = 2
deg(d), deg(h),deg(y),deg(f) = 3
deg(p),deg(j),deg(q),deg(m),deg(o) = 4
Thus, not every vertex has a degree of at least 8.5, and Dirac's Theorem cannot be applied to
guarantee the existence of a Hamiltonian cycle in this graph.
Ore's Theorem:
Ore's Theorem states that if, for every pair of non-adjacent vertices in a graph, the sum of their
degrees is at least n, where n is the total number of vertices, then the graph is guaranteed to have a
Hamiltonian cycle.
In the provided graph:
- The total number of vertices (n) is 17.
However:
- The sum of the degrees of non-adjacent vertices is lesser than 17, violating the condition set by
Ore's Theorem. Therefore, Ore's Theorem cannot be applied to guarantee the existence of a
Hamiltonian cycle in this graph.

So we need to use something harder like Backtracking :

Backtracking Steps:
Start at a Vertex: Choose a starting vertex, let's say 'x'.
Explore Paths: At each step, explore paths to adjacent unvisited vertices.
Mark and Unmark: Mark a vertex as visited, explore, and unmark if the path doesn't lead to a
Hamiltonian path.
Backtrack: If a dead end is reached, backtrack to the previous vertex.
Starting at 'x', let's explore all possible paths using backtracking:
x-y-j-i-p-o-d-e-f-g-h-q-k-c-l-m-n-x
x-y-j-i-p-o-d-e-f-g-h-q-k-c-l-m-n-x
x-y-j-i-p-o-d-e-f-g-h-k-q-c-l-m-n-x
x-y-j-i-p-o-d-e-f-g-h-k-c-l-m-n-q-x
x-y-j-i-p-o-d-e-f-g-h-c-k-q-l-m-n-x
x-y-j-i-p-o-d-e-f-g-h-c-l-m-n-q-k-x
x-y-j-i-p-o-d-e-f-g-h-l-q-k-c-m-n-x
x-y-j-i-p-o-d-e-f-g-h-l-m-n-q-k-c-x
x-y-j-i-p-o-d-e-f-g-h-l-c-k-q-m-n-x
x-y-j-i-p-o-d-e-f-g-h-l-m-n-c-k-q-x
x-y-j-i-p-o-d-e-f-g-h-l-c-q-k-m-n-x
x-y-j-i-p-o-d-e-f-g-h-l-m-c-k-q-n-x
x-y-j-i-p-o-d-e-f-g-h-l-m-n-q-c-k-x
x-y-j-i-p-o-d-e-f-g-h-l-n-q-k-c-m-x
x-y-j-i-p-o-d-e-f-g-h-l-n-m-c-q-k-x
x-y-j-i-p-o-d-e-f-g-h-n-q-k-c-l-m-x
x-y-j-i-p-o-d-e-f-g-h-n-m-l-c-q-k-x
x-y-j-i-p-o-d-e-f-g-h-n-l-q-k-c-m-x
After exploring these paths, we can observe that no path visits each vertex exactly once, violating
the Hamiltonian path condition. Repeatedly, we encounter situations where a vertex is revisited
before all other vertices are visited, confirming the absence of a Hamiltonian path in this graph.

Reference
GeeksforGeeks. (2024) 'Types of Binary Tree', GeeksforGeeks, Available at:
https://www.geeksforgeeks.org/types-of-binary-tree/
Rosen, K. H. (2024) Discrete Mathematics and Its Applications, Available at:
https://drive.google.com/file/d/0B073BLiAJ6_gSzYyR1lBMDlfaGc/view?resourcekey=0-bjzV-nJxf-
bRCap9m8ZwEg
Wikipedia. (2024) 'Union', Wikipedia, Available at: https://en.wikipedia.org/wiki/Union
Wikipedia. (2024) 'Intersection', Wikipedia, Available at:
https://en.wikipedia.org/wiki/Intersection
Wikipedia(2024) 'Nguyên lý bao hàm-loại trừ', Wikipedia, Available at:
https://vi.wikipedia.org/wiki/Nguy%C3%AAn_l%C3%BD_bao_h%C3%A0m-
lo%E1%BA%A1i_tr%E1%BB%AB