top of page
Math 314: Graph Theory
Lecture:

TR 11:00am–12:15pm.

001 Carver Hall.
Office hours:

379 Carver Hall.

Monday 8:3010: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: cutvertices  Lec11b  Lec11f  HW05  HW05sols 
Feb 23  Connectivity revisited: blocks  Lec12b  Lec12f  
Feb 28  Vertex and edgeconnectivity  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 vertexcovers  Lec17b  Lec17f  HW08  HW08sols 
Mar 30  Edge and vertex independence and covering numbers  Lec18b  Lec18f  
April 4  Vertexcoloring and chromatic numbers  HW09  
April 6  Chromatic numbers continued 
Source files for assignments
bottom of page