Mat 516, Graph Theory Web Page
Announcements
Midterm: 11/15.
List of Theorems for the midterm test: pdf.
Homework 3 (Due 11/13) Chapter 2: 18, 21, 24 (EE: 20, 23, 26) Chapter 10: 1, 11 (EE: 1, 11).
Problem *: Prove Lemma 1.9.2 Problem **: Let (H,G) be in family F (Section 2.4) and e be an edge not in the union of E(H) and E(G). Then H+e, G+e contain cycles C and D. Show (without applying Lemma 2.4.3) that the union of V(C) and V(D) is connected in both H and G.
Homework 2 (Due 10/13), Problem *: Use Hall's Theorem to prove Tutte's Theorem.
Chapter 2: 1, 8, 11, 13, 15. (Electronic Edition Problems: 1, 10, 13, 15, 17)
Homework 1 (Due 09/06), Chapter 1: 2, 5, 7, 8, 15.
Please read: R. Rizzi, A short proof of Konig's matching theorem, Journal of Graph Theory 33 (3) (2000) 138-139. (Also available here.)
List of Theorems for the midterm test: pdf.
Homework 3 (Due 11/13) Chapter 2: 18, 21, 24 (EE: 20, 23, 26) Chapter 10: 1, 11 (EE: 1, 11).
Problem *: Prove Lemma 1.9.2 Problem **: Let (H,G) be in family F (Section 2.4) and e be an edge not in the union of E(H) and E(G). Then H+e, G+e contain cycles C and D. Show (without applying Lemma 2.4.3) that the union of V(C) and V(D) is connected in both H and G.
Homework 2 (Due 10/13), Problem *: Use Hall's Theorem to prove Tutte's Theorem.
Chapter 2: 1, 8, 11, 13, 15. (Electronic Edition Problems: 1, 10, 13, 15, 17)
Homework 1 (Due 09/06), Chapter 1: 2, 5, 7, 8, 15.
Please read: R. Rizzi, A short proof of Konig's matching theorem, Journal of Graph Theory 33 (3) (2000) 138-139. (Also available here.)
Tests
There will be a midterm exam and a take-home final.
Links
Doug West's Open Problems Archive is
here.
Comments
Please send an email if you have comments.