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 MidSemester 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 (21, Deo), Subgraph (22, 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 2527, Wilson)
 Eulerian Graphs(3.5, Wilson)
 Randomly Traceable Graphs (28, 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 240241)
 Spanning Trees, Fundamental Circuits, Finding All Spanning trees
 Shortest Spanning Trees: Prim's and Kruskal's algorithms
Week 6: Cutsets and Cutvertices [Chapter 4, Deo]  Cutsets, Properties of a cutset
 All cutsets in a graph (Proof of Theorem 44 is excluded, example is included)
 Fundamental circuits and cutsets
 Connectivity and Separability (up to Theorem 410)
Week 7: Matrix Representations of Graphs [Chapter 7, Deo] Incidence Matrix (page 137139)
 Adjacency Matrix (157161)
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.117.5
Week 11: Coloring of Graphs [Continued], Directed Graphs  Brook's Theorem (618, without Proof), Coloring Maps (619, Up to Theorem 19.1)
 Coloring Edges (620, Up to Theorem 20.2), Chromatic Polynomials (621)
 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 142 (Without Proof)
 Extensions of the MaxFlow Mincut theorem (142)
 Multicommodity Flow (144)
Week 14: Graph Theory in Operations Research (Chapter 1410, Deo): Game Theory Graphs in Game theory
 Types of Games
 The example of Nim the game
 Kernel (Theorem 145, excluding the proof), Winning strategy

Updating...
Ċ Mohiuddin Khan, Dec 29, 2013, 11:52 PM
