top of page
Math 314: Graph Theory
Lecture:
-
TR 11:00am–12:15pm.
-
001 Carver Hall.
Office hours:
-
379 Carver Hall.
-
Monday 8:30-10:00am and 4:00–5:30pm.
Textbook:
A first course in graph theory, by Gary Chartrand and Ping Zhang.
Schedule and assignments
-
Homework assignments are due by the beginning of the lecture on the date by which they are posted (table below).
-
The preferred submission type is on paper before the class begins.
-
If you are unable to attend class when an assignment is due, you can email your assignment to sanmarco@iastate.edu.
-
Your submission must be a single .pdf file. Please include MATH 314 and the homework number in the subject line.
-
-
Late submissions will incur a 1% penalty per minute of being late.
Dates | Topics | Lec(blank) | Lec(filled) | HW(pdf) | HW(sols) |
|---|---|---|---|---|---|
Jan 17 | Basic definitions and important terminology: walks, paths, cycles. Connectivity | Lec01b | Lec01f | ||
Jan 19 | Connectivity (continued), some special graphs, bipartite graphs. | Lec02b | Lec02f | ||
Jan 24 | Special graphs, complements, join and product, vertex degrees, handshaking lemma. | Lec03b | Lec03f | HW01 | HW01sols |
Jan 26 | Degrees and connectivity, regular graphs | Lec04b | Lec04f | ||
Jan 31 | Degree sequences, Havel–Hakimi Theorem, Erdös–Gallai Theorem (one direction). | Lec05b | Lec05f | HW02 | HW02sols |
Feb 2 | Adjacency matrix. Isomorphisms and automorphisms | Lec06b | Lec06f | ||
Feb 7 | Trees and forests | Lec07b | Lec07f | HW03 | HW03sols |
Feb 9 | Trees and forests continued, spanning trees | Lec08b | Lec08f | ||
Feb 14 | Minimum spanning trees, Kruskal's algorithm, Prim's algorithm | Lec09b | Lec09f | HW04 | HW04sols |
Feb 16 | Enumerating tress: Prüfer codes | Lec10b | Lec10f | ||
Feb 21 | Connectivity revisited: cut-vertices | Lec11b | Lec11f | HW05 | HW05sols |
Feb 23 | Connectivity revisited: blocks | Lec12b | Lec12f | ||
Feb 28 | Vertex- and edge-connectivity | Lec13b | Lec13f | HW06 | HW06sols |
Mar 2 | Connectivity continued, Menger's Theorem | Lec14b | Lec14f | ||
Mar 7 | Discussion session | DS01 | |||
Mar 9 | Midterm | Midsols | |||
Mar 14 | Spring Break | ||||
Mar 16 | Spring Break | ||||
Mar 21 | Eulerian circuits and trails in multigraphs | Lec15b | Lec15f | HW07 | HW07sols |
Mar 23 | Hamiltonian cycles and paths | Lec16b | Lec16f | ||
Mar 28 | Matchings, edge- and vertex-covers | Lec17b | Lec17f | HW08 | HW08sols |
Mar 30 | Edge- and vertex- independence and covering numbers | Lec18b | Lec18f | ||
April 4 | Vertex-coloring and chromatic numbers | Lec19b | Lec19f | HW09 | HW09sols |
April 6 | Chromatic numbers, critical graphs and trees | Lec20b | Lec20f | ||
April 11 | Edge-chromatic numbers | Lec21b | Lec21f | HW10 | HW10sols |
April 13 | Factorization, edge-chromatic numbers continued | Lec22b | Lec22f | ||
April 18 | Planar graphs, Euler's identity | Lec23b | Lec23f | HW11 | HW11sols |
April 20 | Planar graphs continued: 5- and 6-color theorems, Kuratowski's Theorem | Lec24b | Lec24f | ||
April 25 | Ramsey numbers | Lec25b | Lec25f | HW12 | HW12sols |
April 27 | Ramsey numbers continued, lower bounds | Lec26b | Lec26f | ||
May 2 | Review session | HW13 | HW13sols | ||
May 4 | Discussion session | DS02 | |||
May 10 | Final Exam. Location: Carver 001. Time: 9:45 - 11:45 AM.
All materials covered on or after Feb 28 might be evaluated. See the file DS02 for details |
Source files for assignments
bottom of page