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.
Quiz Marks Quiz marks, along with attendance and midsemester marks, is uploaded (see the file section below). I have found one script each in Quiz #1 and Quiz #2 without any student id written on it. If you are one of them, or if you think your marks are entered wrong, please contact me by Tuesday, 8 May. Update: The missing roll numbers, for quiz 1 and 2, are 094427 and 094420, respectively. An updated version of the mark sheet is was uploaded.
Quiz #1 Date Announced The first quiz will be held on Tuesday, 17 January at 10 am. The syllabus is the contents covered in the first three weeks.
Quiz #2 Date Announced The second quiz will be held on Sunday, 12 February at 2 pm. The syllabus is the contents covered in weeks 4 to 7.
Quiz #3 Date Announced The third quiz will be held on 28 March 1 April at 2 pm. The syllabus is the contents covered in weeks 11 to 13 (Planarity and Matrices).
Quiz #4 Date Announced The fourth quiz will be held on Monday, 16 April at 2 pm. The syllabus is the contents covered in the weeks 14 and 15.
Timeline:  Week 1: Introduction, History, Definitions, Incidence and Degree (Chapter 1, Deo. Excluding pages 5 and 6)
 Week 2:
 Some important graphs (Null, Complete, Regular, Platonic, Bipartite, Cubes etc) (Section 2.3, Wilson)
 Isomorphism (2.1, Deo)
 Subgraphs (2.2, Deo)
 Walks, Paths and Circuits (2.4, Deo)
 Connected, Disconnected graphs (2.5, Deo)
 Matrix Representation (Page 14, Wilson)
 Week 3:
 Theorem 23 (Deo)
 Eight circles problem, Six people at a party (Section 2.4, Wilson)
 Euler graphs:
 Definition, Euler's Theorem (with proof), Fleury's algorithm (without proof) (3.6, Wilson)
 Randomly/Arbitrarily traceable graphs (2.8, Deo)
 Hamiltonian graphs:
 Definitions, (3.7, Wilson, excluding theorem 7.1)
 Week 4:
 Some algorithms (3.8, Wilson): Shortest path problem, The Chinese postman problem, The travelling salesman problem
 Week 5:
 Trees (Chapter 3, Deo): Definition, Properties, Distance and Centers
 Week 6:
 Trees: Rooted and binary trees, Counting trees
 Week 7:
 Trees: Spanning Trees, Fundamental Circuits, Finding all spanning trees of a graph, Spanning trees in a weighted graph
 Week 8:
 Cutsets and cutvertices (Chapter 4, Deo) : Cutsets, Properties of cutsets, all cutsets in a graph, fundamental cutsets, connectivity and separability.
 Week 9, 10:
 Week 11: Planar and Dual graphs (Chapter 5, Deo)
 Introduction, Kuratowski's two graphs, detection of planarity (5.1  5.5)
 Week 12: Planar and Dual graph (Chapter 5, Deo)
 Homeomorphic graphs, Geometric dual, combinatorial dual, selfdual graphs, thickness and crossing (5.6, 5.7, 5.9)
 Euler's formula (Theorem 56. The proof of this theorem is shown from page 66 of Wilson)
 Week 13: Matrix representation of graphs (Chapter 7, Deo)
 Incidence matrix ( 7.1, upto page 139)
 Circuit matrix (7.3, excluding theorem 7.4)
 Fundamental circuit matrix (7.4, pages 144 and 145)
 Cutset matrix (Only definition and example, excluding the properties)
 Adjacency matrix (7.9, pages 157160)
 Week 14: Colouring graphs (Chapter 6, Wilson)
 Colouring vertices (6.17)
 Colouring maps (6.19, up to theorem 19.4)
 Week 15:
 Colouring edges (6.20, up to theorem 20.3)
 Chromatic Polynomial (6.21)
 Digraphs (7.22, Wilson, up to theorem 22.1 excluding the proof)+(7.23, up to theorem 23.3 excluding the proof)
 Week 16: Graph Theory in Operations Research (Chapter 14, Deo)
 Transport networks (14.1, Excluding "Linear programming formulation")
 Theorem 14.1 (without proof), theorem 14.2 (without proof, but with example)
 Extensions of maxflow mincut theorem (14.2)
Textbooks:  Graph theory with applications to engineering and computer science, Narsingh Deo (Available in IUT Library and Nilkhet)
 Introduction to graph theory, Fourth Edition, Robin J. Wilson (PDF available; contact with me)
 Discrete Mathematics and Its Applications, Sixth Edition, Kenneth H. Rosen
