MATH2069 Discrete Mathematics and Graph Theory
This page contains information on the Intermediate Unit of Study MATH2069 Discrete Mathematics and Graph Theory.
This unit is offered in Semester 1.
Lecturer(s): Alexander Molev
You may also view the description of MATH2069 in the central units of study database.
- Credit point value: 6CP.
- Classes per week: Three lectures, one tutorial and one practice class.
Email enquiries about MATH2069 may be sent to MATH2069@maths.usyd.edu.au.
Students: Please give your name and SID when emailing us. Anonymous emails will not be replied to.
MATH2069/2969 Information in 2016
Name: Prof Alexander Molev
Room: Carslaw 707
Phone: 9351 5793
Consultation hour: Tuesday 2-3 pm
Lectures and practice classes (joint for MATH2069 and MATH2969) will be held in Carslaw 159 at the following times:
- Monday 2-3 pm
- Tuesday 3-4 pm
- Wednesday 2-3 pm
- Thursday 1-2 pm
In general, lectures are held in the Monday-Wednesday times and practice classes in the Thursday times. The exceptions to the latter are Weeks 5 and 11, when the Thursday time will be a quiz, and Weeks 12 and 13, when the Thursday time will be a revision lecture.
In the practice classes you will work through a sheet of questions relating to the material in the preceding lectures; the solutions will be briefly discussed in the class. These questions will be similar to those in the quizzes. The question sheets are printed at the back of the books of lecture notes (see below), and also available on the web resources page, where the solutions will be posted after each week's class.
Tutorials (one per week) start in Week 2. The tutorial sheets are printed at the back of the books of lecture notes. (They will not be distributed in tutorials.) They are also available on the web resources page, where the solutions will be posted. The tutorials in Week 13 will be opportunities for you to try past exam questions; specifically, the 2015 exam papers will be useful practice.
Your raw mark will be calculated as follows.
- 70%: Exam
- 20%: Class quizzes (two, worth 10% each)
- 10%: Assignment
The two quizzes (the same for MATH2069 and MATH2969) will be held in weeks 5 and 11, during the Thursday 1-2pm class times (not in the tutorials). The quizzes consist of short-answer questions where only the answers will be marked, similar to the practice class questions. More information on these quizzes will be posted on the web resources page closer to the dates.
The assignment (different for MATH2069 and MATH2969) will be posted on the web resources page and will be due on Thursday April 28.
Texts and References
The examinable content of the unit is all contained in the books of lecture notes: Topics in Discrete Mathematics and Introduction to Graph Theory by Anthony Henderson. These may be purchased from Kopystop, 55 Mountain Street, Broadway. Kopystop's phone number is 9211 2733.
Some other reference books, which you may want to consult for additional examples and exercises, are listed on the Acknowledgements page of the two books of lecture notes.
In the first half, we will study several related areas of discrete mathematics, which have applications throughout pure and applied mathematics, as well as in computer science and other sciences. In the second half, we will restrict our attention to one particular area of discrete mathematics, namely graph theory. We will investigate some of the fundamental results on Eulerian and Hamiltonian graphs, trees, and vertex colourings, among other topics.
The sections expected to be covered in each week's lectures (approximately) are as follows.
Week 1: Introduction to discrete mathematics, sets and functions,
counting principles (0,1.1)
Week 2: Ordered selections, binomial coefficients (1.2,1.3)
Week 3: Inclusion/exclusion, Stirling numbers (1.4,1.5)
Week 4: Recursive sequences, induction, homogeneous linear recurrences (2.1,2.2,2.3)
Week 5: Non-homogeneous recurrences, formal power series (2.4,3.1,3.2)
Week 6: Generating functions and recursion (3.3)
Week 7: Introduction to graph theory, basic definitions (0,1.1,1.2)
Week 8: Degrees, Eulerian and Hamiltonian graphs (1.3,2.1,2.2)
Week 9: Minimal walks, trees (2.3,3.1)
Week 10: Spanning trees, Matrix-Tree Theorem (3.2,3.3)
Week 11: Vertex colourings, chromatic polynomial (4.1,4.2)
Week 12: Edge colourings (4.3) and revision.
Week 13: Revision
Objectives and outcomes
The objectives of this course are to:
introduce basic concepts of combinatorics - permutations, selections and arrangements;
introduce the concept of generating functions;
illustrate how to find solutions of recurrence relations;
introduce the classes of Eulerian and Hamiltonian graphs, trees and weighted graphs;
illustrate how to find minimal walks in graphs;
introduce vertex and edge colourings of graphs;
illustrate how to find chromatic polynomials of graphs.
Students who successfully complete this course should be able to:
identify and use combinatorial objects involved in counting problems to solve them;
solve linear recurrence relations by using generating functions and characteristic equations;
identify Eulerian and Hamiltonian graphs;
apply special algorithms to find minimal walks in weighted graphs;
apply special algorithms to find spanning trees in graphs;
find chromatic numbers and chromatic polynomials of graphs.
The distinction in the expected outcomes between the advanced and normal streams
will be in the depth of understanding the theoretical base of the subject. The advanced class students should be able to reproduce the proofs of the basic theorems considered in the course and use them to solve problems by producing their own arguments. The focus of the normal level stream will be on practical skills relied on the methods and approaches developed in the course. They will be expected to be able to explain only the most basic arguments underlying these methods.