UNIVERSITY EXAMINATIONS
JANUARY/FEBRUARY 2025
MAT4846
GRAPH THEORY II
Welcome to the MAT4846 examination
Date: 20 January 2025
Time: 08:00 – 11:00
Hours: 3
Examiner name: PROF Z I ALI
Internal moderator name: PROF T NAZIR
External moderator name: PROF Y HARDY
This paper consists of 5 pages (including the cover page).
Total marks: 100
Instructions:
• Include reference to additional information sheets if applicable.
• You are NOT allowed to use any calculator.
• No typed solutions will be accepted and the script will be cancelled
• You need to declare your honesty regarding writing this paper.
• This exam is IRIS invigilated. You must have your camera on for entire duration of the
• exam. Failure to have your camera on for the duration of the exam, will lead to disciplinary
• action taken against you.
Additional student instructions
1. Students must upload their answer scripts in a single PDF file (answer scripts must not be
password protected or uploaded as “read only” files)
2. Incorrect file format and uncollated answer scripts will not be considered.
3. NO emailed scripts will be accepted.
4. Students are advised to preview submissions (answer scripts) to ensure legibility and that
the correct answer script file has been uploaded.
5. Incorrect answer scripts and/or submissions made on unofficial examinations platforms
(including the invigilator cell phone application) will not be marked and no opportunity will
be granted for resubmission. Only the last answer file uploaded within the stipulated
submission duration period will be marked.
6. Mark awarded for incomplete submission will be the student’s final mark. No opportunity for
resubmission will be granted.
7. Mark awarded for illegible scanned submission will be the student’s final mark. No
opportunity for resubmission will be granted.
8. Submissions will only be accepted from registered student accounts.
9. Students who have not utilised the proctoring tool will be deemed to have transgressed
Unisa’s examination rules and will have their marks withheld. If a student is found to have
been outside the proctoring tool for a total of 10 minutes during their examination session,
they will be considered to have violated Unisa’s examination rules and their marks will be
, withheld. For examinations which use the IRIS invigilator system, IRIS must be recording
throughout the duration of the examination until the submission of the examinations scripts.
10. Students have 48 hours from the date of their examination to upload their invigilator results
from IRIS. Failure to do so will result in students deemed not to have utilized the proctoring
tools.
11. Students suspected of dishonest conduct during the examinations will be subjected to
disciplinary processes. Students may not communicate with any other person or request
assistance from any other person during their examinations. Plagiarism is a violation of
academic integrity and students who plagiarise, copy from published work or Artificial
Intelligence Software (eg ChatGPT) or online sources (eg course material), will be in
violation of the Policy on Academic Integrity and the Student Disciplinary Code and may be
referred to a disciplinary hearing. Unisa has a zero tolerance for plagiarism and/or any
other forms of academic dishonesty.
12. Listening to audio (music) and making use of audio-to-text software is strictly prohibited
during your examination session unless such usage of the software is related to a student’s
assistive device which has been so declared. Failure to do so will be a transgression of
Unisa’s examination rules and the student's marks will be withheld.
13. Students are provided 30 minutes to submit their answer scripts after the official
examination time. Students who experience technical challenges should report the
challenges to the SCSC on 080 000 1870 or their College exam support centres (refer to
the Get help during the examinations by contacting the Student Communication Service
Centre [unisa.ac.za]) within 30 minutes. Queries received after 30 minutes of the official
assessment duration time will not be responded to. Submissions made after the official
assessment time will be rejected according to the examination regulations and will not be
marked. Only communication received from your myLife account will be considered.
14. Non-adherence to the processes for uploading assessment responses will not qualify the
student for any special concessions or future assessments.
15. Queries that are beyond Unisa’s control include the following: a. Personal network or
service provider issues
b. Load shedding/limited space on personal computer
c. Crashed computer
d. Non-functioning cameras or web cameras
e. Using work computers that block access to the myExams site (employer firewall
challenges)
f. Unlicensed software (eg license expires during exams)
Postgraduate students experiencing the above challenges are advised to apply for an
aegrotat and submit supporting evidence within ten days of the examination session.
Students will not be able to apply for an aegrotat for a third examination opportunity.
Postgraduate/undergraduate students experiencing the above challenges in their second
examination opportunity will have to reregister for the affected module.
16. Students suspected of dishonest conduct during the examinations will be subjected to
disciplinary processes. UNISA has a zero tolerance for plagiarism and/or any other forms
of academic dishonesty.
17. Students experiencing network or load shedding challenges are advised to apply together
with supporting evidence for an Aegrotat within 3 days of the examination session.
, QUESTION 1
(a) Define each of the following concepts:
(i) A Tree. Illustrate your answer with an example of a tree. (4)
(ii) A block. Illustrate your answer with an example of a graph and write draw the blocks separately. (4)
(iii) A bipartite graph. Give an example of tree bipartite graphs. (3)
(iv) A bridge. (3)
(b) State and prove Ore’s Theorem. (6)
(c) Assume that a graph T is a tree. Prove that there exists a unique path joining every two distinct vertices (5)
in T .
[25]
QUESTION 2
(a) Consider a connected graph G with order n and size m. Prove by induction on the number of edges of G (5)
that n − 1 ≤ m.
(b) Consider a tree T of order n that contains exactly vertices of degree 1 or 4. Prove that T contains (5)
(n − 2)/3 vertices of degree 4.
(c) If G is a connected graph with cycle. For u, v ∈ G such that G − u and G − v are trees, show that the (4)
vertices u and v have the same degree.
(d) Let G be a graph of order n and size m.
(i) Define the minimum degree of a graph, δ(G). (1)
n
(ii) Prove that every graph G with oder at at least three and minimum degree δ(G) ≥ 2 has a Hamil- (4)
tonian cycle.
(e) Define the following:
(i) Hamiltonian graph. (2)
(ii) Eulerian graph. Illustrate the definition with several examples. (2)
(iii) Planar graph. Illustrate the definition with several examples. (2)
[25]
[TURN OVER]
JANUARY/FEBRUARY 2025
MAT4846
GRAPH THEORY II
Welcome to the MAT4846 examination
Date: 20 January 2025
Time: 08:00 – 11:00
Hours: 3
Examiner name: PROF Z I ALI
Internal moderator name: PROF T NAZIR
External moderator name: PROF Y HARDY
This paper consists of 5 pages (including the cover page).
Total marks: 100
Instructions:
• Include reference to additional information sheets if applicable.
• You are NOT allowed to use any calculator.
• No typed solutions will be accepted and the script will be cancelled
• You need to declare your honesty regarding writing this paper.
• This exam is IRIS invigilated. You must have your camera on for entire duration of the
• exam. Failure to have your camera on for the duration of the exam, will lead to disciplinary
• action taken against you.
Additional student instructions
1. Students must upload their answer scripts in a single PDF file (answer scripts must not be
password protected or uploaded as “read only” files)
2. Incorrect file format and uncollated answer scripts will not be considered.
3. NO emailed scripts will be accepted.
4. Students are advised to preview submissions (answer scripts) to ensure legibility and that
the correct answer script file has been uploaded.
5. Incorrect answer scripts and/or submissions made on unofficial examinations platforms
(including the invigilator cell phone application) will not be marked and no opportunity will
be granted for resubmission. Only the last answer file uploaded within the stipulated
submission duration period will be marked.
6. Mark awarded for incomplete submission will be the student’s final mark. No opportunity for
resubmission will be granted.
7. Mark awarded for illegible scanned submission will be the student’s final mark. No
opportunity for resubmission will be granted.
8. Submissions will only be accepted from registered student accounts.
9. Students who have not utilised the proctoring tool will be deemed to have transgressed
Unisa’s examination rules and will have their marks withheld. If a student is found to have
been outside the proctoring tool for a total of 10 minutes during their examination session,
they will be considered to have violated Unisa’s examination rules and their marks will be
, withheld. For examinations which use the IRIS invigilator system, IRIS must be recording
throughout the duration of the examination until the submission of the examinations scripts.
10. Students have 48 hours from the date of their examination to upload their invigilator results
from IRIS. Failure to do so will result in students deemed not to have utilized the proctoring
tools.
11. Students suspected of dishonest conduct during the examinations will be subjected to
disciplinary processes. Students may not communicate with any other person or request
assistance from any other person during their examinations. Plagiarism is a violation of
academic integrity and students who plagiarise, copy from published work or Artificial
Intelligence Software (eg ChatGPT) or online sources (eg course material), will be in
violation of the Policy on Academic Integrity and the Student Disciplinary Code and may be
referred to a disciplinary hearing. Unisa has a zero tolerance for plagiarism and/or any
other forms of academic dishonesty.
12. Listening to audio (music) and making use of audio-to-text software is strictly prohibited
during your examination session unless such usage of the software is related to a student’s
assistive device which has been so declared. Failure to do so will be a transgression of
Unisa’s examination rules and the student's marks will be withheld.
13. Students are provided 30 minutes to submit their answer scripts after the official
examination time. Students who experience technical challenges should report the
challenges to the SCSC on 080 000 1870 or their College exam support centres (refer to
the Get help during the examinations by contacting the Student Communication Service
Centre [unisa.ac.za]) within 30 minutes. Queries received after 30 minutes of the official
assessment duration time will not be responded to. Submissions made after the official
assessment time will be rejected according to the examination regulations and will not be
marked. Only communication received from your myLife account will be considered.
14. Non-adherence to the processes for uploading assessment responses will not qualify the
student for any special concessions or future assessments.
15. Queries that are beyond Unisa’s control include the following: a. Personal network or
service provider issues
b. Load shedding/limited space on personal computer
c. Crashed computer
d. Non-functioning cameras or web cameras
e. Using work computers that block access to the myExams site (employer firewall
challenges)
f. Unlicensed software (eg license expires during exams)
Postgraduate students experiencing the above challenges are advised to apply for an
aegrotat and submit supporting evidence within ten days of the examination session.
Students will not be able to apply for an aegrotat for a third examination opportunity.
Postgraduate/undergraduate students experiencing the above challenges in their second
examination opportunity will have to reregister for the affected module.
16. Students suspected of dishonest conduct during the examinations will be subjected to
disciplinary processes. UNISA has a zero tolerance for plagiarism and/or any other forms
of academic dishonesty.
17. Students experiencing network or load shedding challenges are advised to apply together
with supporting evidence for an Aegrotat within 3 days of the examination session.
, QUESTION 1
(a) Define each of the following concepts:
(i) A Tree. Illustrate your answer with an example of a tree. (4)
(ii) A block. Illustrate your answer with an example of a graph and write draw the blocks separately. (4)
(iii) A bipartite graph. Give an example of tree bipartite graphs. (3)
(iv) A bridge. (3)
(b) State and prove Ore’s Theorem. (6)
(c) Assume that a graph T is a tree. Prove that there exists a unique path joining every two distinct vertices (5)
in T .
[25]
QUESTION 2
(a) Consider a connected graph G with order n and size m. Prove by induction on the number of edges of G (5)
that n − 1 ≤ m.
(b) Consider a tree T of order n that contains exactly vertices of degree 1 or 4. Prove that T contains (5)
(n − 2)/3 vertices of degree 4.
(c) If G is a connected graph with cycle. For u, v ∈ G such that G − u and G − v are trees, show that the (4)
vertices u and v have the same degree.
(d) Let G be a graph of order n and size m.
(i) Define the minimum degree of a graph, δ(G). (1)
n
(ii) Prove that every graph G with oder at at least three and minimum degree δ(G) ≥ 2 has a Hamil- (4)
tonian cycle.
(e) Define the following:
(i) Hamiltonian graph. (2)
(ii) Eulerian graph. Illustrate the definition with several examples. (2)
(iii) Planar graph. Illustrate the definition with several examples. (2)
[25]
[TURN OVER]
