Math 3322: Graph Theory (Spring 2021)

General Information

Instructor: Mikhail Lavrov
Location: Mathematics Building 218
Lecture times: 9:05am-9:55am on Monday if your last name begins A-L and on Wednesday if your last name begins M-Z.
Textbook: A First Course in Graph Theory by Chartrand and Zhang, ISBN 0-486-48368-1.
Office hours: Monday 10am-11am and Friday 9am-10am, online via Collaborate Ultra.
D2L page: https://kennesaw.view.usg.edu/d2l/home/2199852.

More information is available on D2L, where I will post the syllabus, homework assignments and solutions, exams, and more. This webpage is primarily for posting recorded lectures.

Homework and Exams

There will be eight homework assignments, two midterm exams, and one final exam. The dates are marked below, but you can find and submit the assignments on D2L. No part of your grade will depend on coming to class.

Detailed Schedule

This is my first time teaching this class at KSU, so the schedule may shift around slightly if a section takes more or less time than I expected.

If you are interested in my slides for this class, the links are below. I don't think that these are a good replacement for coming to class or watching the recorded lectures.

• Slides for Chapters 1-4 (January 11th to February 17th)
• Slides for Chapters 5-7 (February 22nd to March 31st)
• Slides for Chapters 8-10 (April 2nd to May 3rd)

My goal is to have all the recordings for each week posted by the beginning of that week.

• Date
  Textbook
  Recordings
  Assignments
• Mon 1/11
  1.1 Graphs & Graph Models
  • Hello!
  • What are graphs?
  • Examples of graphs
   
• Wed 1/13
  1.2 Connected Graphs
  • Walks in graphs
  • Components
   
• Fri 1/15
  1.2 Connected Graphs
  • Types of walks
  • Subgraphs
   
• Mon 1/18
  No Class
   
   
• Wed 1/20
  Proof methods review
  • About week 2
  • Planning out proofs
  • Proofs about paths
   
• Fri 1/22
  1.3 Common Classes of Graphs
  • Bipartite graphs
  • Common graphs
  HW 1 due
• Mon 1/25
  Induction review
  • About week 3
  • Basics of induction
  • The induction trap
   
• Wed 1/27
  2.1 The Degree of a Vertex
  • Degree definitions
  • Degrees and cycles
   
• Fri 1/29
  2.1 The Degree of a Vertex
  • Diameter 2 graphs
  • Average degree
   
• Mon 2/1
  2.2 Regular Graphs
  • About week 4
  • Harary graphs
  • Many more graphs
   
• Wed 2/3
  2.3 Degree Sequences
  • Degree sequences
  • Edge swap lemma
   
• Fri 2/5
  2.3 Degree Sequences
  • Havel-Hakimi
  • Wrapping up
  HW 2 due
• Mon 2/8
  3.1 The Definition of Isomorphism
  • About week 5
  • Isomorphic graphs
  • Comparing graphs
   
• Wed 2/10
  4.1 Bridges
  • Bridges
  • Intro to trees
   
• Fri 2/12
  4.2 Trees
  • Counting edges
  • Induction on trees
  HW 3 due
• Mon 2/15
  4.2 Trees
  • About week 6
  • Forests
  • Spanning trees
   
• Wed 2/17
  4.3 Spanning Trees
  • Shortest paths
  • MSTs
   
• Fri 2/19
  Exam 1 (due at 11:59pm)
   
   
• Mon 2/22
  5.1 Cut vertices
  • About week 7
  • Cut vertices
  • Some theorems
   
• Wed 2/24
  5.2 Blocks
  • 2-connected graphs
  • Blocks
   
• Fri 2/26
  5.3 Connectivity
  • Vertex connectivity
  • Edge connectivity
   
• Mon 3/1
  5.3 Connectivity
  • About week 8
  • s-t cuts and paths
  • Harary graphs
  HW 4 due
• Wed 3/3
  5.4 Menger's Theorems
  • Menger's theorem
  • Proof of Menger
   
• Fri 3/5
  5.4 Menger's Theorems
  • Applications
  
  
   
• 3/8-3/14
  Spring Break: No Class
   
   
• Mon 3/15
  6.1 Eulerian Graphs
  • About week 9
  • Our two problems
  • Eulerian conditions
   
• Wed 3/17
  6.1 Eulerian Graphs
  • Eulerian graph thm.
  • Gray codes
   
• Fri 3/19
  6.2 Hamiltonian Graphs
  • Tough graphs
  • Dirac's theorem
  HW 5 due
• Mon 3/22
  6.2 Hamiltonian Graphs
  • About week 10
  • Bondy-Chvátal
  • Corollaries
   
• Wed 3/24
  7.1 Strong Digraphs
  • Directed graphs
  • Strong components
   
• Fri 3/26
  7.1 Strong Digraphs
  • Eulerian digraphs
  • De Bruijn graphs
   
• Mon 3/29
  7.2 Tournaments
  • About week 11
  • Acyclic digraphs
  • Tournaments
   
• Wed 3/31
  7.2 Tournaments
  • Hamiltonian cycles
  • Kings
   
• Fri 4/2
  8.1 Matchings
  • Bipartite matching
  • Vertex covers
  HW 6 due
• Mon 4/5
  8.1 Matchings
  • About week 12
  • Kőnig's theorem
  • Hall's theorem
   
• Wed 4/7
  8.1 Matchings
  • 2 more parameters
  • Independent sets
   
• Fri 4/9
  Exam 2 (due at 11:59pm)
   
   
• Mon 4/12
  8.2 Factorization
  • About week 13
  • Matchings & parity
  • Augmenting paths
   
• Wed 4/14
  8.2 Factorization
  • Factorizations
  • Factoring K_n
   
• Fri 4/16
  9.1 Planar Graphs
  • Plane embeddings
  • Regions and faces
   
• Mon 4/19
  9.1 Planar Graphs
  • About week 14
  • Euler's formula
  • Applications
  HW 7 due
• Wed 4/21
  9.1 Planar Graphs
  • Kuratowski's thm.
  • Dual graphs
   
• Fri 4/23
  10.2 Vertex Coloring
  • Vertex coloring
  • Greedy coloring
   
• Mon 4/26
  10.2 Vertex Coloring
  • About week 15
  • Clique numbers
  • The Mycielskian
   
• Wed 4/28
  10.2 Vertex Coloring
  • Random graphs
  • Interval graphs
   
• Fri 4/30
  10.1 The Four Color Problem
  • Six color theorem
  • Tait's attempt
  HW 8 due
• Mon 5/3
  10.3 Edge Coloring
  • Edge coloring
  • Ramsey theory
  • Thank you!
   
• Wed 5/5
  Final Exam (due 5/6 at 11:59pm)