Teaching‎ > ‎

CSE 4533 - Graph Theory

This course is an introduction to the fundamental concepts of graph theory. In the latter portion of the course, we will focus on some advanced materials. Besides, you will also learn about applying graph theoretic approach to solve problems. Please see the attached course outline for a (tentative) schedule and textbooks.

The syllabus of the final exam is all the materials excluding Week 1, Week 2 and Week 6. Proofs of theorems that were covered in the class are included.

  • All the Quiz questions have been uploaded.
  • Quiz #4 will be held on Wednesday, 23 April, at 10.30 in the classroom. Syllabus of the quiz is the materials covered in weeks 11 and 12.
  • Quiz #3 will be held on Tuesday, 01 April, at 2.00 pm, in the classroom. Update: Quiz will be on Wednesday 10.30 am.
  • Syllabus of the quiz is the materials covered in weeks 8,9,10.
  • Syllabus of Mid-Semester Examination is all the materials covered in the 7 weeks.
  • Quiz #2 will be held on Wednesday, 19 February, at class time. Syllabus of the quiz is Trees, Chapter 3 of Deo. 
  • Quiz #1 will be held on Monday, 27 January, at 2.00 pm, in the classroom. Syllabus of the quiz is the materials covered in the first three weeks.

Week 1: Introduction [Chapter 1, Deo]
  • What is a Graph?
  • Application of Graphs: Koenigsberg Bridge Problem, Three Utilities Problem
  • Finite and Infinite Graphs
  • Isolated vertex, Pendant vertex, Null Graph
Week 2: Definitions and Examples
  • Definitions, Isomorphism, Connectedness, Adjacency, Subgraphs, Matrix Representations (2.2, Wilson)
  • More on Isomorphism (2-1, Deo), Subgraph (2-2, Deo)
  • Examples: Null, Complete, Cycle, Path,Wheel, Regular, Platonic, Bipartite, Cube Graphs, Complement of a Graph  (2.3, Wilson)
  • Puzzles: Eight Circle Problem, Six People at a Party (2.4, Wilson)
Week 3: Paths and Cycles
  • Connectivity (Page 25-27, Wilson)
  • Eulerian Graphs(3.5, Wilson)
  • Randomly Traceable Graphs (2-8, Deo)
  • Hamiltonian Graphs (3.6, Wilson)
  • Some Algorithms: Shortest Path, Chinese Postman, Travelling Salesman (3.7, Wilson)
Week 4: Trees [Chapter 3, Deo]
  • Definition, Properties
  • Distance, Centers of Trees
  • Rooted Tree, Binary Tree, Weighted Path Length
Week 5: Trees [Continued]
  • Counting Trees, Cayley's Theorem (Proof from Chapter 10, Page 240-241)
  • Spanning Trees, Fundamental Circuits, Finding All Spanning trees
  • Shortest Spanning Trees: Prim's and Kruskal's algorithms
Week 6: Cut-sets and Cut-vertices [Chapter 4, Deo]
  • Cut-sets, Properties of a cut-set
  • All cut-sets in a graph (Proof of Theorem 4-4 is excluded, example is included)
  • Fundamental circuits and cut-sets 
  • Connectivity and Separability (up to Theorem 4-10)
Week 7: Matrix Representations of Graphs [Chapter 7, Deo]
  • Incidence Matrix (page 137-139)
  • Adjacency Matrix (157-161)
Week 8: Planar and Dual Graphs [Chapter 5, Deo]
  • Combinatorial vs Geometric Graphs
  • Planar Graphs
  • Kuratowski's Two Graphs
Week 9: Planar and Dual Graphs [Continued]
  • Regions, Infinite Regions
  • Euler's Formula (Proof from Wilson, Page 66)
  • Detection of Planarity
Week 10: Planarity [Continued], Coloring of Graphs [Chapter 6, Wilson]
  • Geometric Dual, Combinatorial dual
  • Thickness and Crossing
  • Coloring of Graphs (Chapter 6, Wilson): Coloring Vertices::Theorems 17.1-17.5
Week 11: Coloring of Graphs [Continued], Directed Graphs
  • Brook's Theorem (6-18, without Proof), Coloring Maps (6-19, Up to Theorem 19.1)
  • Coloring Edges (6-20, Up to Theorem 20.2), Chromatic Polynomials (6-21)
  • Digraphs (Chapter 7, Wilson. Up to Page 105)
  • DAG, Topological Sorting (Refer to the PDF- 18.1.2, Without Proofs)
Week 12: Matching of Graphs (Refer to the uploaded PDF)
  • Matching: Definition, Stable and Perfect Matching, Will you marry me?
  • Stable Marriage Problem, Finding the Stable Matching, TMA: Algorithm, Example
  • TMA: All the Theorem, Lemma and their proofs are included. Only the proof of Theorems 4 and 5 are excluded.
Week 13: Graph Theory in Operations Research (Chapter 14, Deo): Transport Networks
  • Transport Networks (14.1 Excluding the linear programming part)
  • Theorem 14-2 (Without Proof)
  • Extensions of the Max-Flow Min-cut theorem (14-2)
  • Multicommodity Flow (14-4)
Week 14: Graph Theory in Operations Research (Chapter 14-10, Deo): Game Theory
  • Graphs in Game theory
  • Types of Games
  • The example of Nim the game
  • Kernel (Theorem 14-5, excluding the proof), Winning strategy

Mohiuddin Khan,
Dec 29, 2013, 11:52 PM