Instructor: Hemanshu Kaul

Office: 125C, Rettaliata Engg Center.
Phone: (312) 567-3128
E-mail: kaul [at] iit.edu

Time: 11:25am, Monday and Wednesday
Place: 124, Rettaliata Engg Center

Office Hours: Changed; see Online Course Structure Below - Monday: 12:40-1:15pm and 4:30-5:30pm [Problem Solving Session], Wednesday: 12:40-1:15pm, and by appointment (send email).
Emailed questions are also encouraged.

TA Office Hours: Changed; see Online Course Structure Below - Gunjan Sharma, Monday: 9-10am and 12:45-1:45pm, Wednesday: 1:45-2:45pm, in RE 129. (You may also consult Quinn Stratton; see the schedule at the Math TA Office in RE 129).

• Monday, 2/20 : See the important changes due to online instruction in the "Course Information" section above and the "Class Log" section below.



• Wednesday, 2/5 : Dates for Mid-term Exams #1 and #2 have been announced. Look below in the appropriate section.


• Monday, 1/13 : Check this webpage regularly for homework assignments, announcements, etc.

• Exam # 1 : Wednesday, February 26th. Syllabus: Based on topics corresponding to HWs #1 to #5 [total 9 lectures].
• Exam # 2 : Wednesday, April 15th. Syllabus: Based on topics corresponding to HWs #6 to #10 [total 11 lectures]. See new details in the document `Online Course Structure' above.
• Final Exam : Monday, May 4th, 2-4pm. Topics: All topics studied during the semester.

• Wednesday, 1/15 : Read and understand Examples 1.1.30, 1.1.31, 1.1.33, and 1.1.35 from Section 1.1.


• Homework #1 : Due Wednesday, 1/22. Solutions distributed on 1/29
  Warm-Up Exercises: Section 1.1 - #2, #3, #4, #5, #8, #10, #33.
  Suggested Problems: Section 1.1 - #12, #17, #21, #22, #24, #26, #31, #35.
  Written Problems: Homework 1: Problems for submission
  Some comments on the HW.


• Wednesday, 1/22 : Read and understand Definitions 1.1.27 and 1.2.2, and Examples 1.2.3 and 1.2.4.


• Monday, 1/27 : [Optional] Read about an exciting development regarding graph isomorphism.


• Homework #2 : Due Wednesday, 1/29. Solutions distributed on 2/3.
  Warm-Up Exercises: Section 1.2 - #2, 6, 9.
  Suggested Problems: Section 1.1 - #24, 25, 27, 30. Section 1.2 - #14, 17, 18, 20, 22, 28.
  Written Problems: Homework 2: Problems for submission
  


• Wednesday, 1/29 : Read and understand Definition 1.2.21, Examples 1.2.21 and Theorem 1.2.23.


• Homework #3 : Due Wednesday, 2/5. Solutions distributed on 2/10.
  Warm-Up Exercises: Section 1.2 - #1, 2, 5, 6, 9, 10, 11.
  Suggested Problems: Section 1.2 - #25, 38, 40, 41.
  Written Problems: Homework 3: Problems for submission
  


• Wednesday, 2/5 : Read and understand Example 1.3.10 and Proposition 1.3.15.


• Homework #4 : Due Wednesday, 2/12. Solutions to be distributed on 2/17.
  Warm-Up Exercises:Section 1.3 - #1, 2, 3, 4, 5, 7.
  Suggested Problems: Section 1.3 - #10, 14, 17, 26, 41, 46, 59, 63.
  Written Problems: Homework 4: Problems for submission
  


• Monday, 2/10 : Read and understand Example 1.3.20.
  Read and understand Example 1.3.24, and Remark 1.3.25.


• Wednesday, 2/12 : Review the following Definitions, Examples and Propositions discussed in class: 1.4.1, 1.4.2, 1.4.3, 1.4.6, 1.4.9, 1.4.10, 1.4.11, 1.4.12, 1.4.13, 1.4.17, 1.4.18, 1.4.22, 1.4.23, 1.4.24, 1.4.27, 1.4.29, 1.4.30.


• Homework #5 : Due Wednesday, 2/19. Solutions distributed on 2/19.
  Warm-Up Exercises: Section 1.4 - #1, 2, 4, 5, 8.
  Suggested Problems: Section 1.4 - #10, 14, 19or20, 25, 29, 36, 37.
  Written Problems: Homework 5: Problems for submission
  


• Homework #6 : Due Wednesday, 3/4. Solutions distributed on 3/9.
  Warm-Up Exercises: Section 2.1 - #11, 12, 13, 15, 16. Section 2.2 - #1, 2, 3.
  Suggested Problems: Section 2.1 - #26, 33, 39, 44, 47, 51, 55, 59, 60, 63. Section 2.2 - #6, 10, 16, 17, 18.
  Written Problems: Homework 6: Problems for submission
  


• Monday, 3/2 : [Optional] Read Ringel's Conjecture 2.2.13 from 1964 and the article describing its solution in 2020!
  Also read Definition 2.2.14 and the still unsolved Graceful Labeling Conjecture 2.2.15 from 1964, followed by Theorem 2.2.16.
  And a bit more here.


• Wednesday, 3/4 : Read and understand Algorithm 2.3.1 and its Example 2.3.2. We will also discuss it in class on Monday.


• Homework #7 : Due Wednesday, 3/11. Solutions distributed on 3/11.
  Warm-Up Exercises: Section 2.3 - #1, 2, 3, 5.
  Suggested Problems: Section 2.2 - #6, 7, 8, 10, 16, 17, 18. Section 2.3 - #7, 10, 14, 15.
  Written Problems: Homework 7: Problems for submission
  


• Wednesday, 3/11 : [Optional] Try the two `Graphs and Matrices' problems distributed in class today. They will give you an interesting perspective on how linear algebra can be used to solve graph theory problems.


• Wednesday, 3/11 : Read and understand the statement and proof of Corollary 3.1.13 to Hall's Theorem.


• Homework #8 : Due Wednesday, 3/25. Solutions distributed on 3/31.
  Warm-Up Exercises: Section 3.1 - #1, 2, 3, 4, 5, 6, 11.
  Suggested Problems: Section 3.1 - #8, 9, 30, 31, 32, 36, 40, 42.
  Written Problems: Homework 8: Problems for submission
  


• Homework #9 : Due Thursday, 4/2. Solutions distributed on 4/3.
  Warm-Up Exercises: Section 3.3: #1, 2, 3, 4, 5. 4.1: #1, 3, 4, 5.
  Suggested Problems: Section 4.1: #8, 10, 14, 15, 19, 24, 25, 27, 28, 29, 31, 35.
  Written Problems: Homework 9: Problems for submission
  


• Homework #10 : Due Thursday, 4/9. Solutions distributed on 4/10.
  Warm-Up Exercises: Section 4.2: #1, 2, 4, 6.
  Suggested Problems: Section 4.2: #9, 12, 14, 18, 20, 22, 23, 24, 28.
  Written Problems: Homework 10: Problems for submission
  


• Monday, 4/6 : [Optional] Read more about the recent improvement in the Hadwiger-Nelson problem on the chromatic number of the unit-distance graph on the plane in these articles:
  Overview of the construction of the improved lower bound
  and
  Basic introduction to the problem


• Wednesday, 4/8 : [Optional] There are many graph products other than Cartesian Product. We proved a simple formula for chromatic number of Cartesian product, but the chromatic number of the Tensor Product is not known. Hedetneimi's conjecture on the chromatic number of Tensor Product of Graphs has recently been disproved (after standing for over 50 years). You can read about the conjecture and related results in its wikipedia article. Read about the reactions from mathematicians to its disproof as well as a high-level description of the counterexample here.
  But the best way to truly understand the construction of the counterexample is to watch this lecture/talk by Xuding Zhu (an expert in graph coloring who also proved a fractional version of the Hedeneimi conjecture).


• Homework #11 : Due Thursday, 4/23.
  Warm-Up Exercises: Section 5.1: 1, 3, 4, 5, 7, 9, 12, 14. Section 5.2: #1, 2, 3, 5. Section 7.1: #1, 2, 4.
  Suggested Problems: Section 5.1: #20, 21, 22, 32, 33, 34, 35, 38, 39, 41, 42, 47, 48, 50, 51. Section 5.2: #7, 9, 16, 17, 23, 34, 37, 38, 39, 40. Section 7.1: #11, 18, 22, 26, 27, 33, 34.
  Written Problems: Homework 11: Problems for submission
  


• Monday, 4/20 : [Optional] Read more about the simple yet mysterious Jordan Curve Theorem:
  A beautiful discussion with illustrations of why Jordan Curve Theorem is difficult
  Tverberg's elementary proof of JCT from 1980.
  Thomassen's amazing proof of JCT based on the trivial result that K_{3,3} is non-planar, followed by a graph-theoretic proof of the Jordan-Schonflies Theorem and and the classification of compact surfaces!!
  A discussion by Thomas Hales about geometric intuition underlying Thomassen's proof of JCT and how it can be made into a formal computer verifiable argument
  


• Homework #12 : [Optional; replaces one previous lower HW score] Due Thursday, 11/30.
  Warm-Up Exercises: Section 6.1: #1, 3, 4, 5, 7, 8, 9. Section 6.2: #1, 2ab, 4. Section 6.3: #2(Do you recognize this!), 3(Aha!).
  Suggested Problems: Section 6.1: #18, 21, 25. Section 6.2: #5, 10, 12. Section 6.3: #5.
  Written Problems: One of {Section 5.1: #31, or Section 7.1: #24}. One of {Section 5.2: #11, or #15}. Section 6.1: #26. Section 6.2: #7. Section 6.3: #12.

• Monday, 1/13 : Graph definitions and models - acquaintance relations, degree of a vertex, complement, Ramsey problem, clique, independent set, job assignments, bipartite graphs and matchings, scheduling, proper coloring and chromatic number. (From Section 1.1)
• Wednesday, 1/15 : : Subgraph, connected graph, adjacency and incidence matrices and their properties, isomorphism, Different ways of proving isomorphism and non-isomorphism, unlabeled representatives of paths, cycles, complete graphs, complete bipartite graphs, isomorphism class as an equivalence relation. (From Section 1.1)
  Comment: Read about an exciting development regarding graph isomorphism.
• Monday, 1/20 : Holiday.
• Wednesday, 1/22 : Discussion of some HW problems. Isomorphism class through equivalence relation, Decomposition of a graph, self-complementary graphs and decomposition of K_n, Petersen graph - definition, and properties, Petersen graph - girth and its proof; u,v-walk, trail and path. (From Sections 1.1 and 1.2)
• Monday, 1/27 : u,v-walk, trail and path, Every u,v-walk contains a u,v-path, connected - graph, pair of vertices, components, number of vertices, edges and components, Induced subgraph vs ordinary subgraph, cut-edge, cut-vertex. (From Sections 1.1 and 1.2)
• Wednesday, 1/29 : Characterization of cut-edge, Odd cycle in odd walk, Maximal vs Maximum, Degree bounds and existence of paths and cycles through proofs by extremality, Characterization of bipartite graphs. (From Section 1.2)
• Monday, 2/3 : Characterization of bipartite graphs, Konigsberg problem and Eulerian circuits, Characterization of Eulerian graphs, Even graphs decompose into cycles. (From Section 1.2)
• Wednesday, 2/5 : Notation related to degree, neighborhood, order and size, Double counting and the degree-sum formula with its corollaries, d-dimensional Hypercubes, Some structural properties of hypercubes, Extremal problems and the structure of their proofs, min number of edges in a connected graph, Mantel's theorem. (From Sections 1.2 and 1.3)
• Monday, 2/10 : Proof of Mantel's theorem, Smallest minimum degree that implies connectedness, MAX-CUT and analysis of the local switching algorithm. (From Section 1.3)
• Wednesday, 2/12 : Two ways of writing the same proof using algorithm vs extremality, Degree sequences and their characterization, Graphic sequences and their characterization (Havel-Hakimi Theorem), Directed graphs and related terminology and concepts, Connectivity in Digraphs, Degree sum formula for digraphs, Eulerian Digraphs and their characterization. (From Sections 1.3 and 1.4)
• Monday, 2/17 : Orientations of undirected graphs, Tournaments, Existence of Kings in a Tournaments, Forests, Trees, Spanning Trees, Leafs and induction on Trees, Four equivalent characterizations of Trees. (From Sections 1.4 and 2.1)
• Wednessday, 2/19 : Four equivalent characterizations of Trees, Some elementary properties of Spanning trees and trees - how to convert one spanning tree into another, Local Search Algorithms over graphs of solutions, Erdos-Sos conjecture and related result. (From Section 2.1)
• Monday, 2/24 : Review for Exam. Distance related terminology in graphs, Relation between the diameter a graph and its complement, Center of a tree. (From Sections 2.1 and 2.2)
• Wednesday, 2/26 : Exam #1.
• Monday, 3/2 : Wiener index and its minimization and maximization for trees and general graphs, Counting spanning trees in a graph - edge contraction and a recursive formula. (From Sections 2.1 and 2.2)
• Wednesday, 3/4 : Counting spanning trees in a graph, Matrix tree theorem (without proof), Cayley's formula and Prufer's code for number of labeled trees on n vertices, An application of Prufer's code for counting spanning trees of K_n with prescribed degrees. Discussion of Exam 1 grades, score distribution, and solutions. (From Section 2.2)
• Monday, 3/9 : Discussion of Exam 1 solutions. Weighted graphs, Minimum spanning tree and Kruskal's algorithm, Shortest distances and Djikstra's algorithm. (From Section 2.3)
• Wednesday, 3/11 : The rooted tree generated by Djikstra's Algorithm, Breadth-first Search, Matchings and perfect matchings, perfect matchings in K_n,n and K_n, Maximal vs. Maximum matchings, Alternating and augmenting paths, Components of symmetric difference of two matchings, Characterization of maximum matching in terms of non-existence of augmenting paths, Hall's condition and Hall's Theorem for Bipartite graph Matchings, Perfect matchings in k-regular bigraphs. (From Sections 2.3 and 3.1)


ONLINE TEACHING BEGINS:


• Week of March 23rd : Lectures available at Youtube (through your IIT account): Week of March 23rd Lectures
  Proofs of Berge's Theorem, and of Hall's Theorem for Bipartite graph Matchings, Perfect matchings in k-regular bigraphs. Relation between max matching and min vertex cover - equality for bipartite graphs (Konig-Egervary Theorem), relation between max ind. set and min edge cover - equality for bipartite graphs [Konig], Relation between vertex cover and independent sets, relation between edge cover and matchings [Gallai's Theorem]. k-factors, odd components and Tutte's condition for 1-factors. Vertex-connectivity of a graph, difference between k-connected and connectivity = k, Connectivity of complete bipartite graphs and d-dimensional hypercubes. (From Sections 3.1, 3.3, and 4.1)


• Week of March 30th : Lectures available at Youtube (through your IIT account): Week of March 30th Lectures
  Minimum number of edges in a k-connected graph on n vertices and Harary graphs, edge-connectivity of a graph, difference between an edge-cut and a disconnecting set, Relation between connectivity, edge-connectivity, and minimum degree, Proof of Relation between connectivity, edge-connectivity, and minimum degree, 3-regular graphs have the same connectivity and edge-connectivity, Counting edges in an edge-cut, Bond and its characterizing property, Blocks and how they decompose a graph. Equivalent structural properties of 2-connected graphs, Expansion Lemma. x,y-cut and internally disjoint x,y-paths, and their min-max relation, Menger's Local connectivity Theorem and the corresponding dual optimization problems. How to show the optimal value for dual optimization problems using weak duality, Line graph and the translation of connectivity to edge-connectivity, Proof of Menger's Theorem for local edge-connectivity, Menger's Global Theorem for connectivity and edge-connectivity. (From Sections 4.1 and 4.2.)


• Week of April 6th and part of April 13th : Lectures available at Youtube (through your IIT account): Week of April 6th (and April 13th) Lectures. There is one extra short video for April 13th. Next playlist of videos will be for the week of April 20th.
  Vertex coloring - motivation and examples, proper k-coloring and k-partite graphs, Lower bounds on the chromatic number in terms of clique number and independence number, Greedy coloring and upper bound on chromatic number, Brook's theorem, Greedy coloring w.r.t vertices ordered from high degree to low and the corresponding upper bound on chromatic number, Color-critical or k-critical graphs and why they matter, An upper bound on chromatic number using color-critical subgraph (useful proof idea), Mycielski's construction of triangle-free graphs with arbitrarily high chromatic number, Intersection graphs, Interval graphs and their chromatic number (through greedy coloring), Cartesian Product of graphs and their chromatic number. Edge coloring, relation between edge-chromatic number of G and chromatic number of L(G), Vizing-Gupta theorem (without proof) and Class 1 and Class 2 graphs (but edge-chromatic number remains a hard problem), How multigraphs effect the edge-chromatic number - fat triangle and Shannon's and Vizing-Gupta bounds on edge-chromatic numbers of multigraphs, Bipartite Graphs are Class 1. (From Sections 5.1, 5.2, 7.1.)


• Wednesday, 4/15 : Mid-term Exam #2. See the document `Online Course Structure' above.


• Week of April 20th : Lectures available at Youtube (through your IIT account): Week of April 20th Lectures.
  Maximum number of edges in an r-colorable graph, Turan graph, Turan's theorem and its proof, Comments on Erdos-Stone theorem, Hajos conjecture and Hadwiger conjecture - graph subdivisions and graph minors.
  Drawings, planar graph, and plane graph, K_5 and K_{3,3} are not planar, Dual of a plane graph, length of the faces, Euler's Theorem n-e+f=2, edge bound for planar graphs, Kuratowski's Theorem and characterization of planarity, outerplanar graphs - properties, non-examples, How existence of small degree vertex in Trees, Outerplanar graphs, and Planar graphs gives an easy bound on their chromatic number. (From Sections 5.2, 6.1, 6.2 and 6.3).


• Week of April 27th : Lectures available at Youtube (through your IIT account): Week of April 27th Lectures.
  Four and Five color theorems for Planar graphs. (From elsewhere.)
  Review of old topics, Discussion of Exam#2, Discussion regarding Final Exam.

• Wikipedia: Graph Theory
• Mathworld : Graph Theory Dictionary
• Glossary of terms in combinatorics


• Mathpages: Combinatorics
• Dynamic Surveys in Combinatorics
• Combinatorial Software and Databases
• Combinatorial Object Server


• Textbooks for alternative points of view and for additional applications:
  
  • Modern Graph Theory, B. Bollobas.
  • Graph Theory (2008 edition), Bondy and Murty.
  • Graph Theory, by R. Diestel
  • Digraphs: Theory, Algorithms and Applications, by Bang-Jensen, Gutin.
  
  
  • Algorithmic graph theory and perfect graphs, 2nd edition Martin Golumbic.
  • Graphs and Applications: An Introductory Approach, J.M.Aldous and R.J.Wilson.
  • Graph Theory Applications, L.R.Foulds.
  • Topics in Intersection Graph Theory, T.A.McKee and F.R.McMorris
  • Bipartite Graphs and their Applications, A.S.Asratian, T.MJ Denley, R.Haggkvist
  
  

  ---

  
  
  
  HOME