Math 412
Introduction to Graph Theory
Sections D13 and D14
Instructor: Alexandr Kostochka
Office: 234 Illini Hall
Phone: (217) 265-8037 (office)
Fax: (217) 333-9576
E-mail:
kostochk@math.uiuc.edu
Time and place: 11am-11:50am MWF, 243 Altgeld Hall
Final exam:
7:00 - 10:00 PM, Monday, May 10
Office hours: 3-4pm Monday and Friday, 4-5pm Wednesday, and by
appointment
Class Announcements
We have help sessions on Tuesdays, from 5pm to 6:30pm in 141 Altgeld Hall.
All our evening tests will be in Room 143 Altgeld Hall:
Test 1: Tuesday, February 16, 7pm-8:30pm;
Test 2: Tuesday, March 16, 7pm-8:30pm;
Test 4: Tuesday, April 27, 7pm-8:30pm.
We also will have Test 3 in class on Wednesday, April 7.
Topics for Test 1 are:
0. Definitions.
1. Bipartite graphs. A characterization of bipartite graphs.
2. Isomorphism of graphs.
3. Representations of graphs: adjacency and incidence matrices.
4. Eulerian circuits and trails. Euler Theorem.
5. Extremal problems on graphs. Mantel's Theorem.
6. Graphic sequences. A theorem on such sequences.
7. Directed graphs: degrees, connectivity, Eulerian circuits, de Bruijn
graphs.
8. Tournaments, kings in tournaments.
Topics covered by Quiz 2 are:
1. A characterization of bipartite graphs.
2. Degree Sum Formula.
3. Euler's Theorem.
4. Graphic sequences. Havel-Hakimi Theorem.
5. Mantel's Theorem on maximum number of edges in
triangle-free graphs.
6. Definitions about directed graphs.
7. De Bruijn graphs.
8. Kings in tournaments. A theorem on the existence of kings.
9. Trees. A characterization theorem for trees.
10. Distance in graphs: eccentricity, diameter, radius,center.
Jordan's theorem on centers of trees.
To look at your grades, go to
``www.math.uiuc.edu'', then ``courses'', then ``scores reports''.
Last changed on February 8, 2010.