MTH3170 - Network mathematics - 2019

6 points, SCA Band 2, 0.125 EFTSL

Undergraduate - Unit

Refer to the specific census and withdrawal dates for the semester(s) in which this unit is offered.



Organisational Unit

School of Mathematical Sciences

Chief examiner(s)

Professor David Wood


Professor David Wood

Unit guides



  • Second semester 2019 (On-campus)


Students must have passed one of the following units: MTH1035, MTH2025, MTH2121, MTH2140, MTH3110, MTH3121, MTH3140 or FIT2014


This unit provides an introduction to graph theory, which is the mathematics of networks. Topics covered include trees, Eulerian tours, Hamiltonian cycles, shortest path problem, bipartite graphs, matchings, graph colouring, max-flow problem, graph connectivity, independent sets, planarity, random graphs. Applications to a variety of the sciences will be presented. Students will learn how to write proofs and analyse algorithms.


On completion of this unit students will be able to:

  1. Apply the basic concepts of graph theory.
  2. Demonstrate the importance and breadth of applications of graph theory in mathematics and the sciences, especially computer science.
  3. Apply some of the most famous theorems of graph theory such as the max-flow-min-cut theorem, the marriage theorem, and the 4-colour theorem.
  4. Construct and write mathematical proofs of theorems about graphs.
  5. Execute, analyse and prove correctness of algorithms for solving various graph optimisation problems.
  6. Demonstrate advanced problem solving skills, both individually and collectively with staff and fellow students.
  7. Demonstrate advanced skills in the written and oral presentation of mathematical arguments.


NOTE: From 1 July 2019, the duration of all exams is changing to combine reading and writing time. The new exam duration for this unit is 3 hours and 10 minutes.

End of semester examination (3 hours): 60% (Hurdle)

Continuous assessment: 40% (Hurdle)

Hurdle requirement: To pass this unit a student must achieve at least 50% overall and at least 40% for both the end-of-semester examination and continuous assessment components.

Workload requirements

  • Three 1-hour lectures per week
  • One 2-hour applied class per week
  • Seven hours of independent study per week

See also Unit timetable information

This unit applies to the following area(s) of study