THE UNIVERSITY OF
SYDNEY

MATH2009 GRAPH
THEORY

**COURSE INFORMATION 2004**

#### Lectures

Three lectures per week:
Monday 2 pm in Carslaw 173

Wednesday 2 pm in Carslaw 173

Friday 2 pm in Carslaw 173

Lectures run for 13 weeks. The last lecture will therefore be on Friday 29 October.
#### Lecturer

Sandra Britton

Room: Carslaw 521

Phone: 9351 4077

email: S.Britton@maths.usyd.edu.au

#### Tutorials

Tutorials (one per week) start in week 2. You should attend the tutorial given on your timetable.
Printed tutorial sheets will be distributed in lectures. Any spare sheets will be placed in the wooden boxes in
the corridor on Level 7 of Carslaw.
Tutorial sheets will also be available
here.
#### Assessment

Your final raw mark for this unit will be calculated as follows:
70%: Two-hour exam at end of semester 1.

10%: Assignment mark.

20%: Quiz mark.

#### Assignments

Two assignments will be collected and marked. Each assignment is worth 5% of
your final raw mark.

Assignments will be due (in room 521)
by 1 pm on ** Friday 27 August** and ** Friday 8 October**.

You are encouraged to work with others in solving the assignment problems, but
the work submitted must be your own.

Marked assignments will be returned to the pigeonholes on Carslaw Level 3.

#### Quizzes

Two quizzes will be held during the lecture hour, on ** Wednesday 8 September **
and ** Wednesday 20 October.**

Each quiz is worth 10% of your final raw mark.

#### Reference books

There is no textbook, but *Introduction to Graph Theory *by Robin Wilson
is a very useful reference book.

Also recommended is * the little blue book* by Britton, Coleman and Henderson, which
contains useful stuff from first year mathematics.

Both books are available at the Co-op Bookshop.
Another useful reference book is * Discrete Mathematics with Graph Theory*
by Edgar Goodaire and Michael Parmenter.

#### Solutions

Tutorial and assignment solutions will be available
here.
#### Consultation Times

I will try to be in my office every Monday from 1pm - 2pm, for consultation.
However, you are welcome to come and see me at other times if I am not busy.
#### The aims of this course

To interest you in the subject matter of Graph Theory.
To illustrate some of the widespread applications of Graph Theory.
To encourage the development of methods of thinking which will be of
benefit in some 3rd year mathematics courses, and in many other
areas of applied mathematics and technology.
To extend your appreciation of mathematics,
and to convince you that there is much more to it than just being able to
handle the mechanics of evaluating integrals or solving equations.
#### The objectives of this course

By the end of this course, students should:

know the meaning of the following terms (in the context of Graph Theory):
graph, vertex, edge, digraph, simple, complete, bipartite, degree of a vertex, degree sequence,
isomorphic, walk, trail, path, cycle, connected, subgraph, Eulerian, Hamiltonian, tree, planar.
be able to determine whether or not a graph is Eulerian, and find an Euler trail.
be able to apply the shortest path algorithm,
Kruskal's algorithm, Prim's algorithm, the algorithm for finding a maximum flow and a
minimum cut in a transport network.
be able to count the number of spanning trees, using the matrix tree theorem.
be able to determine chromatic numbers, chromatic indices and chromatic polynomials.
know the hand-shaking lemma, Euler's formula for planar graphs,
and Hall's theorem on matching, and use these results in problem solving.
know what is meant by the 4-colour map problem, and its solution.
be able to find the critical path in an activity network.
#### The syllabus

A weekly outline of the content covered in lectures will be provided
here.

Back to MATH2009 page.