Math 3322: Graph Theory (Spring 2022)

General Information

Instructor: Mikhail Lavrov
Location: Architecture 173
Lecture times: 5:00pm to 6:15pm on Monday and Wednesday
Office hours: Tuesday 11am-12pm and Wednesday 2pm-3pm in my office (D245, in the Math building)
D2L page: https://kennesaw.view.usg.edu/d2l/home/2509877.

D2L will be used to submit assignments (these will be posted both here and on D2L, for convenience) and to view grades. The syllabus will also be posted there.

Homework and Exams

There will be eight homework assignments, two midterm exams, and one final exam; the dates are marked below.

I will post the homework assignments here and on D2L; they are always due on Friday at 11:59pm, via D2L, with the exception of the last assignment, which is due on Monday, instead.

Exams will be given in person during our ordinary 75-minute class period. (At least that's the current plan. I will update this schedule and send the class an email if the plan changes.)

Textbooks

There is no official textbook for this course. I will publish lecture notes on this page before each class; all the material covered will be in those lecture notes.

If you would like additional references, I recommend the following:

  • Chartrand and Zhang, A First Course in Graph Theory. This textbook is used by many other sections of Math 3322 (so some of you may already have it); it is also an inexpensive paperback.
  • West, Introduction to Graph Theory. This is a very comprehensive resource, going into much more detail than we will on many topics. If you are reading it, read it slowly and carefully: a single page often corresponds to 10-15 minutes of class time!

Detailed Schedule

I will use the labels CZ and W to indicate which sections of the textbooks I mentioned above will correspond to which day of class. (We might not always cover everything in those sections, especially in W.)

If you are looking for the lecture notes originally found on this page, I have removed them because I've posted new and improved lecture notes on the page for fall 2023 instead.

  • Date
    Topic Covered
    Other details
  • Mon 1/10
    Introduction to graphs
    CZ 1.1, W 1.1
  • Wed 1/12
    Connected components
    CZ 1.2, W 1.2
  • Mon 1/17
    No class
     
  • Wed 1/19
    Proof techniques
    W App. 3
    HW 1 due Friday
  • Mon 1/24
    Types of graphs
    CZ 1.3, W 1.1-1.2
  • Wed 1/26
    Proofs by induction
    W App. 3
  • Mon 1/31
    The degree of a vertex
    CZ 2.1, W 1.3
  • Wed 2/2
    Regular graphs
    CZ 2.2, W 1.3
    HW 2 due Friday
  • Mon 2/7
    Graphic sequences
    CZ 2.3, W 1.3
  • Wed 2/9
    Isomorphic graphs
    CZ 3.1, W 1.1
  • Mon 2/14
    Trees and spanning trees
    CZ 4.1, W 2.1
  • Wed 2/16
    Properties of trees
    CZ 4.2, W 2.1
    HW 3 due Friday
  • Mon 2/21
    Cayley's formula
    CZ 4.4, W 2.2
  • Wed 2/23
    Exam 1
     
  • Mon 2/28
    Bipartite matchings
    CZ 8.1, W 3.1
  • Wed 3/2
    König's theorem
    W 3.1-3.2
    HW 4 due Friday
  • Mon 3/7
    No class
     
  • Wed 3/9
    No class
     
  • Mon 3/14
    Matchings in general graphs
    CZ 8.1, W 3.3
  • Wed 3/16
    Digraphs and multigraphs
    CZ 7.1, W 1.4
  • Mon 3/21
    Eulerian graphs
    CZ 6.1, W 1.2
  • Wed 3/23
    Hamiltonian graphs
    CZ 6.2, W 7.2
    HW 5 due Friday
  • Mon 3/28
    Tournaments
    CZ 7.2, W 1.4
  • Wed 3/30
    Planar graphs
    CZ 9.1, W 6.1
  • Mon 4/4
    Planarity testing
    CZ 9.1, W 6.2
  • Wed 4/6
    Polyhedra
    W 6.1
    HW 6 due Friday
  • Mon 4/11
    Cliques and independent sets
    W 3.1, 5.1
  • Wed 4/13
    Exam 2
     
  • Mon 4/18
    Vertex coloring
    CZ 10.2, W 5.1
  • Wed 4/20
    Bounds on chromatic number
    W 5.1
    HW 7 due Friday
  • Mon 4/25
    Cut vertices
    CZ 5.1, W 4.1
  • Wed 4/27
    k-connectivity
    CZ 5.3, W 4.2
  • Mon 5/2
    Menger's theorem
    CZ 5.4, W 4.2
    HW 8 due Monday
  • Wed 5/4
    Final exam (6pm - 8pm)
     
©