# MATH2069 Discrete Mathematics and Graph Theory

## General Information

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

For further information on Intermediate Mathematics and Statistics, refer to the Intermediate Handbook. In particular, see the MATH2069 handbook entry for further information relating to MATH2069.

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

## Lecturer

**Name:** Prof Alexander Molev

**Room:** Carslaw 707

**Phone:** 9351 5793

**Consultation hour:** Tuesday 2-3 pm

**Email:**
alexander.molev@sydney.edu.au

## Classes

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.

## Assessment

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.

## Course Outline

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.