Introduction to Graph Theory
Math 3260

Announcements:
The midterm exams will be on Monday, February 3 and Monday, March 24
I will give you an extension on the homework assignment #2 until Friday, February 14, 2003 and it should be turned in to Li Gang's mailbox in Ross N524 no later than 2:30pm.
The problem asking for the number of spanning trees of a wheel is hard (although not impossible) and so I am making it a bonus question for the homework assignment. Here is a hint: HINT
The 4th homework assignment is a bit long and we won't get to the topic of the last two problems on the homework until the last day of class so I will make due any 6 of the 8 problems. Hand in your homework either on the last day of class or to the TA's mailbox (Li Gang) in Ross N524 (it is due April 4 at 2:30pm).
I haven't exactly covered every section of the book this term. In class I have covered (at least roughly): Ch 1.1, 2.2, 2.3, 2.4, 3.5, 3.6, 3.7, 3.8, 4.9, 4.10, 5.12, 5.13, 5.14, 5.15, 6.17, 6.21, 8.25, 8.26 and I hope to do 8.29 before the end of class.
The final exam will be Tuesday, April 8 from 12pm-3pm in CLH G.
I will have office hours Monday, April 7 from 2pm-4pm.
(4/9/03) Grades for the course will be posted here in a few weeks.
(4/28/03) I have finished making up the grades. I am posting them here.

York University
Professor Mike Zabrocki
MW 2:30-4pm CLH 110
Office: Ross S615
Office hours: W4-5pm F11:30-1pm
or by appointment
Best way to contact me:






Topics: Graphs, digraphs. Eulerian and Hamiltonian graphs. The travelling salesman. Path algorithms; connectivity; trees; planarity; colourings; scheduling; minimal cost networks. Tree searches and sortings, minimal connectors and applications from physical and biological sciences.


Course description: A first course in graph theory. After considering introductory material on graphs and properties of graphs, we shall look at trees, circuits and cycles. Graph embeddings, labelings and colourings, with some applications, will also be covered.

Prerequisite: At least six credits from 2000-level (or higher) MATH courses (without second digit 5, or second digit 7 in the case of Atkinson), or permission of the instructor.

Text: Introduction to Graph Theory by Robin Wilson (4th ed)

The grade in this course will be based on the following criterion:
1. Homework 20%
2. Midterm exams (2) 40%
3. Final exam 40%

Problem Session: Wednesday 4:30pm N501
Teaching Assistant: Li Gang


The homework is for your benefit so it is in your interest to spend some time doing the problems each week.  Struggle with them for a while before getting help from either myself, the TA, or your fellow students.  Do not copy homework assignments.

Week
Topic/sections in text
Homework
Solutions
1
What is a graph? graph isomorphisms


2
graph isomorphisms, bipartite and regular graphs
HW #1

3
Eulerian and Hamiltonian graphs

HW #1
4
Hamiltonian graphs, algorithms and trees
HW #2

5
Midterm Monday Feb 3, trees


6
Reading week


7
planar graphs, Euler's theorem
HW #3
HW #2
8
dual graphs, graph coloring


9
graph coloring and the 4/5 color theorem


10
coloring polynomial, matching theorem
HW#4
HW #3
11
midterm, transversal theory


12
transversals, flows

HW #4

In class handouts (if you missed a day or lost your copy, they should all be here):
  1. syllabus (1/8/03)
  2. A bunch of pairs of graphs Tell me if they are isomorphic or not (1/13/03)
  3. homework #1 - due: 1/29/03 (1/20/03)
  4. homework #1 solutions
  5. homework #2
  6. homework #2 solutions (2/23/03)
  7. homework #3 (2/24/03)
  8. homework #3 solutions (3/17/03)
  9. homework #4 (3/19/03)
  10. homework #4 solutions (4/2/03)

Links :
  1. Three unsolved math problems worth $1M (NOT!) - one of them is Ramsey theory
  2. a list of the number of graphs with n vertices
  3. The four color theorem