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  Lec19b  Lec19f  HW09  HW09sols 
April 6  Chromatic numbers, critical graphs and trees  Lec20b  Lec20f  
April 11  Edgechromatic numbers  Lec21b  Lec21f  HW10  HW10sols 
April 13  Factorization, edgechromatic numbers continued  Lec22b  Lec22f  
April 18  Planar graphs, Euler's identity  Lec23b  Lec23f  HW11  HW11sols 
April 20  Planar graphs continued: 5 and 6color 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