This syllabus will be updated as the semester progresses.
Be sure to ``refresh'' this page every time you visit;
otherwise, you may be viewing an out-of-date cached copy!
Date Topics
Text Homework
1 9/6
Definition of graphs, multigraphs, digraphs;
The handshake lemma on vertex degree
Lecture 1 Notes
Chapter 1, 1.1-1.3
Chapter 2, Section 1 Assignment 1
Solutions, Assignment 1 2 9/10
Subgraphs; walks, paths, trails and cycles
Proof by induction
Thm: Every (u,v)-walk contains a (u,v)-path
Lecture 2 NotesChapter 1, 1.2
3 9/13
More on walks, paths and cycles;
Connected graphs and connected components;
Bipartite graphsChapter 1, 1.2, 1.3
Assignment 2
Solutions to Assignment 2, Part
I
Solutions to Assignment 2, Part
II4 9/17
Bipartite graphs; algorithm for bipartite-ness
Cycles in bipartite graphsChapter 1, 1.3
5 9/20
Pigeon Hole Principle
Degree sequences, graphicality and a
criterion for graphicalityChapter 2, 2.3
Assignment 3, due September
28
Solutions to Assignment 36 9/24
2-switches and graphicality of degree sequences
Harary regular graphsChapter 2, 2.2, 2.3
7 9/27
Graph Isomorphism
Chapter 3
Assignment 4, due October 4
Solutions to Assignment 4,
part I
Solutions to Assignment 4,
part II
8 10/1
Trees: Introduction
Chapter 4, 4.1, 4.2
9 10/4
Minimum spanning trees;
Kruskal and Prim algorithmsChapter 4, 4.3
Assignment 5, due October
11
Solutions to assignment 5 10 10/8
Optimization and trees;
Breadthfirst and depth-first tree searchesClass Notes
11 10/11
Counting Trees
Chapter 4, 4.4
13 10/18
Dijkstra's algorithm and Breadth-First Search
Class Lecture Notes on
Dijkstra's algorithm
Problems due October 25
Solutions, part 1 12 10/15
First Midterm
Solutions to first midterm
13 10/18
Breadth-First Search and Depth-First Search
Class Notes on Search
Problems due October 25
Solutions, part 1 14 10/22
Prufer coding and counting labelled trees
Class notes on Prufer coding
15 10/25
Cut-vertices
Section 5.1
Problems due November 1
Solutions to Problem Set 7
16 10/29
Blocks and block decomposition
Section 5.2
17 11/1
Connectivity
Section 5.3
Problems due Nov. 8
Solutions to Problem Set 8
18 11/5
Connectivity, Menger's theorem
Section 5.3 and section 5.4
Problems due Nov. 12
Hand in 5.36, and problem 9.
Solutions to 5.34 and
5.36
Solutions to 9A--D
19 11/8
Menger's theorem
Section 5.3
20 11/12
Eulerian graphs
Section 6.1, Class notes
on Euler's theorem and algorithms
21 11/15
Second midterm
22 11/19
Hamiltonian graphs
Section 6.1
23 11/20
Hamiltonian graphs (conclusion)
Matching Sections 6.1, 8.1
Problem Set 10, due Nov. 29
Problem Set 10 Solutions24 11/26
Matching, graph factors
Sections 8.1, 8.2,
Notes on an algorithm for matching
25 11/29
Graph factors; planar graphs
8.2, 9.1
Problem Set 11, due Dec. 6
Problem Set 11 Solutions, part
I
Problem Set 11 Solutions, part
II26 12/3
Planar graphs; Kuratowski's theorem
9.1
27 12/6
Graph Minors and Wagner's theorem;
Graph Coloring (begin) 9.2, 10.1, 10.2
Problem Set 12, due end of
term, 12/13
Hand in 12A, 9.14, 9.32, 10.2
NOTE CORRECTION: Hand in 9.32, not 9.39,
which need not be done at all!
Problem Set 12 Solutions28 12/10
Vertex coloring
10.2 Class notes
29 12/20
Final Exam, Thursday, Dec.20, 12PM-3PM
SEC 206 (usual classroom)
You may bring 3 (single) pages of notes: Check