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 

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:

bottom of page