Graph Theory
Mathematics 428 — Fall 2010

Prof. Weibel

Tentative Course Syllabus   (go to homework table)

Week Lecture dates Sections topics
19/2 (Thurs) 1.1-1.2 Definitions and Degree
29/8(W), 9/9(Th) 1.3; 2.1-2.3Degree, Paths and distance
39/13, 9/16 2.3-2.6Euler and Hamiltonian cycles, Travelling Salesman
49/20, 9/23 3.1-3.3Connectivity and bridges
59/27, 9/30 4.1-4.3Trees
610/4, 10/7 5.1-5.5Vector spaces and graphs
610/11, 10/14 1.1-5.5Review, Midterm
710/18, 10/21 6.1-6.3Factorization and Matchings, Marriage Theorem
810/25, 10/28 7.1-7.3Vertex colorings
911/1, 11/4 7.4-5, 8.1-8.3Edge corings, Planar graphs
1011/8, 11/11 9.1-9.3Labelled graphs
1111/15, 11/18 11.1-11.3Oriented Graphs, Midterm
1211/22-26 ---No classes
1311/29, 12/2 12.1-12.3Critical Paths
1412/6, 12/9 13.1-13.5Network Flows
1512/13(M)Review
XX12/21(Tues)Final Exam (8-11 AM)

Due dateHomework Section/Problems
12/1313.2 #6(ii);    13.4 #3(2),6(i);    13.5 #2,4
12/611.2 #1(iii),6(i),11;    11.3 #1;    12.2 #1,3;    13.1 #2,5
11/158.3 #2;    9.2 #2,7,9 (edge-magic graphs)
9.1: Show that 7-cycles and 8-cycles are graceful. What about hexagons?
11/87.4 #1,4,8;    8.1 #2,4;    8.2 #1(ii,iv),4
11/4 123456    Use the algorithm for Hall's Marriage Theorem to
654321    complete the 2x6 array at left into a 6x6 Latin square.
11/17.1 #3,6,12;    6.2 #2,3    7.3 #1, 6(i,iii,v)
10/256.1 #3,4;    6.2 #2;    6.3 #2,7;
Give a 3-regular graph with no perfect matching.
10/115.2 #3;    5.3 #2;    5.4 #3
10/74.1 #1,7;    4.2 #8;    4.3 #4(i,ii,v),5
Carry out the algorithm of #4.3.5 on the graph in #4(v)
9/303.1 #2,7(iii);    3.2 #2   3.3 #2,5  and:
If G has no cycles, show that every edge of G is a bridge.
9/232.3 #3(i);    2.4 #2,4(i);    2.5 #2,4(i,iii);    2.6 #3(ii)
9/162.1 #6,11,12;   2.2 #3,5,7
9/9/091.1 #3,5;   1.2 #3,11;   1.3 #3,7
Syllabus in Catalogue: Colorability, connectedness, tournaments, eulerian and hamiltonian paths, orientability, and other topics from the theory of finite linear graphs, with an emphasis on applications chosen from social, biological, computer science, and physical problems.


Return to
Top of page    Last updated: Dec. 2010
Return to Main Math 428 page

Charles Weibel / Fall 2010