Contact

Phone: 470-578-7235

Email: mlavrov@kennesaw.edu

Office Location: D 245

Office Hours:
Check the course pages for information about office hours for my classes, or send me an email to make an appointment.

Math 3322: Graph Theory (Fall 2023)

General Information

Instructor: Mikhail Lavrov
Location: Architecture 174
Lecture times: 3:30pm to 4:45pm on Monday and Wednesday
Office hours: 3:30pm to 5:30pm on Thursday in my office, Mathematics 245, or by appointment.
D2L page: https://kennesaw.view.usg.edu/d2l/home/2974260.

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.

During the scheduled office hours, you should feel free to show up with no notice if you have questions of any kind. These are joint office hours for both classes I'm teaching. If you have the flexibility, I would prefer graph theory questions in the first hour, 3:30pm-4:30pm; if not, either hour is fine.

If you cannot make the scheduled office hours, begin by emailing me; if your questions are easy to answer by email, I will do that, and if not, we can find another time to meet. (Allow some time for me to check my email.)

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.

Exams will be given in person during our ordinary 75-minute class period.

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.)

Lecture notes will be available on the day of the lecture or earlier. If you would like to read ahead, check out the page for the previous time I taught this class. (I update my notes every year, so the current ones will be better, but I think the old ones are also pretty good!)

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