Math 314: Graph Theory

Lecture:

Office hours:

Textbook:

A first course in graph theory, by Gary Chartrand and Ping Zhang.

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			HW09
April 6	Chromatic numbers continued

You can find the homework assignments in the table above.

Now, if you wish to typeset your assignments with LATEX, you can use the following files as templates: