Math 350: Graph Theory and Combinatorics (Fall 2017)


Instructor – Jan Volec

Office: Burnside 1242
Office hours: Tuesday, 10:30am - 12:30pm
Contact: jan [AT] ucw [DOT] cz

Course information

Time: Tuesday and Thursday 8:35pm - 9:55pm
Location: Burnside 1B24
Course outline: PDF here
Lecture content: see below
Lecture notes: PDF here (Fall 2012, written by Tommy Reddad)
(The contents and the numbering of the results in the notes differ slightly from the ones in the course.)
Assignments: see below

Midterm

Date: Thursday 19.10. (in-class, open-book)
Topics (tentative):Paths, Cycles, Trees, Bipartite graphs, Matchings in bipartite graphs, Connectivity

Pre-requisites & restrictions

Assignments

DateAssignmentDueSolution
Tue 12.9. Assignment #1 – Paths and CyclesThu 21.9. PDF here
Tue 19.9. Assignment #2 – TreesThu 28.9.

Content of the lectures

DateContent of the lectureLecture notesDiestel's book
Tue 5.9. Introduction to graph theory (see PDF slides from the first lecture) N/AN/A
Thu 7.9. Adjacency & incidence matrices, vertex-degree, walks, trails & paths Chapters 1 & 2Chapter 1
Tue 12.9. Connected components, subgraphs and induced subgraphs, cut-vetices and cut-edgesChapter 2Chapter 1
Thu 14.9. Trees – various characterisations and their mutual equivalenceChapter 3Chapter 1
Tue 19.9. Number of graphs on n vertices and labelled trees on n vertices (Cayley's formula)PDF notesN/A
Thu 21.9. Spanning trees, fundamental cycles, Minimum spanning trees and Kruskal's algorithmChapter 4N/A
Tue 26.9. Plan: Shortest paths and Dijkstra's algorithmChapter 5N/A

Further references & useful links

Grading policy

Course grades will be based upon assignments (20%), a midterm (20%), and a final exam (60%), or, assignments (20%) and a final exam (80%), if this leads to a better mark.