# 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

• MATH 235 (Algebra 1) or MATH 240 (Discrete Structures 1)
• MATH 251 (Honours Algebra 2) or MATH 223 (Linear Algebra)
• Not open to students who have taken / are taking MATH 343 or MATH 340

## 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

• Graph Theory (ETH Zürich) – lecture notes by Benny Sudakov (download PDF)
• Graph Theory – textbook by R. Diestel (available online)
• Introduction to Graph Theory – textbook by D. West
• Combinatorial Problems and Exercises – by L. Lovász, over 600 problems from combinatorics (free access from McGill)