# Graph Theory Mathematics 428 — Fall 2010

### Prof. Weibel

• Lectures: MTh 3 (12:00 - 1:20 AM) in SERC 206 (Busch Campus);
• Text: W. D. Wallis, A Beginner's Guide to Graph Theory (second edition)
Birkhäuser, 2007 (260 pp.); ISBN# 978-0-8176-4484-0
• Weibel's Office hours

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