Instructor: Hemanshu Kaul

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

Time: 1:50pm, Tuesday & Thursday.
Place: 119, Engg. 1 Bldg.

Office Hours: 3:15-4:15pm Tuesday and Thursday, and by appointment.
Emailed questions are also encouraged.

Problem-Solving Session: 4:45pm-5:45pm Tuesday, at 106, E1 bldg.

Graduate Teaching Assistant: Chris Mitillos; cmitillo [at] hawk.iit.edu.
TA Office Hours: 1:30pm-4:30pm Monday, 129, E1 Building.

• Thursday, 9/4 : Tentative Dates for Exam #1, Exam #2, Exam #3, and the Final Exam have been announced below.


• Thursday, 8/28 : HW#1 has been uploaded below. Also see the accompanying comments file.


• Tuesday, 8/26 : Check this webpage regularly for homework assignments, announcements, etc.

• Exam # 1 : Oct 2nd, Thurs. Topics: All the topics (covered in class and through textbook) corresponding to HW#1 to HW#4.
• Exam # 2 : Oct 30, Thurs. Topics: All the topics (covered in class and through textbook) corresponding to HW#5 to HW#7.
• Exam # 3 : Dec 2nd, Tues. Topics:All the topics (covered in class and through textbook) corresponding to HW#8 to HW#10.
• Final Exam : Thursday, December 11th, 2pm to 4pm. Topics: All topics studied during the semester.

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


• Homework #2 : Due Thursday, 9/11. Solutions distributed in class on 9/16, Tuesday.
  Warm-Up Exercises: Section 1.2 - #1, 2, 5, 6, 9, 10, 11.
  Suggested Problems: Section 1.1 - #24, 25, 27. Section 1.2 - #14, 17, 18, 20, 22, 28, 31.
  Written Problems: Homework 2: Problems for submission
  


• Homework #3 : Due Thursday, 9/18. Solutions distributed in class on 9/23, Tuesday.
  Warm-Up Exercises: Section 1.3 - #1, 2, 3, 4, 5, 7.
  Suggested Problems: Section 1.2 - #25, 38, 40, 41. Section 1.3 - #10, 14, 17, 26, 41, 46.
  Written Problems: Homework 3: Problems for submission
  


• Homework #4 : Due Thursday, 9/25. Solutions distributed in class on 9/30, Tuesday.
  Warm-Up Exercises: Section 1.4 - #1, 2, 4, 5, 8.
  Suggested Problems: Section 1.3: #59, 63. Section 1.4 - #10, 14, 20, 29, 37.
  Written Problems: Homework 4: Problems for submission
  


• Special Homework #1 for Math 553 [For grad students not doing a project]: Due Tuesday, October 28th
  Read Section 8.3 (up to the top of page 388) from the book. Then, write-up and submit solutions to FIVE out of the following SEVEN problems: 8.3.2, 8.3.13, 8.3.21, 8.3.27, 8.3.28, 8.3.32a, 8.3.34.


• Homework #5 : Due Thursday, 10/9. Solutions to be distributed in class on Tuesday, 10/14.
  Warm-Up Exercises: Section 2.1 - #11, 13, 15, 16. Section 2.2 - #1, 2, 3.
  Suggested Problems: Section 2.1 - #44, 47, 51, 55, 59, 60, 63. Section 2.2 - #6, 10, 16, 17, 18.
  Written Problems: Homework 5: Problems for submission
  


• Homework #6 : Due Thursday, 10/16. Solutions to be distributed in class on Tuesday, 10/21.
  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 6: Problems for submission
  


• Homework #7 : Due Thursday, 10/23. Solutions to be distributed in class on Thursday, 10/23.
  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 7: Problems for submission
  


• Special Homework #2 for Math 553 [For grad students not doing a project]: Due Tuesday, 11/25.
  Submit a total of FIVE problems from the following list (follow the rules (which allow a choice of up to seven problems out of ten))
  Read pages 87-89 on 'Graceful labeling' and submit 2.2.4&2.2.23.
  Read pages 116-118 on 'Dominating Sets' and submit up to one of {3.1.49&3.1.50, 3.1.51}.
  Read pages 140-141 on 'f-factors of Graphs' and submit 3.3.28.
  Read Section 7.2 (except *-subsections) from page 287 to page 293 and submit up to two out of {7.2.20, 7.2.25, 7.2.26}.
  Read pages 408-412 on 'List coloring and Choosability' (after we finish section 5.1) and submit up to two out of {8.4.21, 8.4.22, 8.4.24}.


• Homework #8 : Due Thursday, 11/6. Solutions distributed in class on Tuesday, 11/11.
  Warm-Up Exercises: Section 3.3: #1, 2, 3, 4, 5. Section 4.1: #1, 3, 4, 5.
  Suggested Problems: Section 3.3: #6, 7, 9, 10, 11, 15, 16, 20, 19, 22, 25, 26,. Section 4.1: # 8, 10, 19, 20, 23.
  Written Problems: Homework 8: Problems for submission
  


• Homework #9 : Due Thursday, 11/13. Solutions distributed in class on Thursday, 11/20.
  Warm-Up Exercises: Section 4.1: #1, 3, 4, 5.. Section 4.2: #1, 2, 4, 6.
  Suggested Problems: Section 4.1: #8, 10, 14, 15, 19, 24, 25, 27, 28, 29, 31, 35. Section 4.2: #9, 12, 14, 18, 20, 22, 23, 24, 28.
  Written Problems: Homework 9: Problems for submission
  


• Homework #10 : Due before 11:59pm, Friday, 11/21. Solutions distributed in class on Tuesday, 11/25.
  Warm-Up Exercises: Section 5.1: 1, 3, 4, 5, 7, 12, 14. 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 7.1: #11, 18, 22, 26, 27, 33, 34.
  Written Problems: Homework 10: Problems for submission
  


• Homework #11 : Due before 11:59pm, Friday, 12/5.
  MATH 454 students have to submit 4 problems and MATH 553 students have to submit 5 problems, out of total 8 choices.
  Warm-Up Exercises: Section 5.1: #9. Section 5.2: #1, 2, 3, 5. 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 7.1: #11, 18, 22, 25, 26, 27, 33, 34. Section 5.2: #7, 9, 16, 17, 23, 34, 37, 38, 39, 40. 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}. Section 7.1: #26, #34. Section 5.2: #11, #15. Section 6.1: #26, #28. Section 6.3: #12.

• Tuesday, 8/26 : Graph definitions and models - acquaintance relations, complement, Ramsey problem, clique, independent set, job assignments, bipartite graphs and matchings, scheduling, proper coloring and chromatic number, Relation between k-partite graph and proper coloring using k colors, Path, cycle. (From Section 1.1)
• Thursday, 8/28 : : Subgraph, connected graph, adjacency and incidence matrices and their properties, degree of a vertex, isomorphism, Different ways of proving isomorphism and non-isomorphism, unlabeled representatives of paths, cycles, complete graphs, complete bipartite graphs, isomorphism class through equivalence relation, Decomposition of a graph, self-complementary graphs and decomposition of K_n, Petersen graph - definition, and properties. (From Sections 1.1 and 1.2)
• Tuesday, 9/2 : Petersen graph - girth & its proof; 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, cut-edge, cut-vertex. (From Sections 1.1 and 1.2)
• Thursday, 9/4 : Induced subgraph, Characterization of cut-edge, Odd cycle in odd walk, Characterization of bigraphs, Union of graphs, Clique as a union of bigraphs. (From Section 1.2)
• Tuesday, 9/9 : Clique as a union of bigraphs, Konigsberg problem and Eulerian circuits, Characterization of Eulerian graphs, Degree bounds and existence of paths and cycles through proofs by extremality, Even graphs decompose into cycles,. (From Section 1.2)
• Thursday, 9/11 : Decomposition by k trails of a graph with 2k odd vertices, notation related to degree, neighborhood, order and size, Double counting and the degree-sum formula with its corollaries, d-dimensional Hypercubes, Some properties of hypercubes, 6-cycles in Petersen graph (read the example). (From Sections 1.2 and 1.3)
• Tuesday, 9/16 : Extremal problems and the structure of their proofs, min number of edges in a connected graph, Smallest minimum degree that implies connectedness, MAX-CUT and analysis of the local switching algorithm, Mantel's theorem. (From Section 1.3)
• Thursday, 9/18 : Proof of Mantel's theorem, Induction trap, 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, Orientations of undirected graphs, Tournaments, Existence of Kings in a Tournaments. (From Sections 1.3 and 1.4)
• Tuesday, 9/23 : Eulerian digraphs and their characterization, 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)
• Thursday, 9/25 : Some elementary properties of Spanning trees and trees - how to convert one spanning tree into another, Erdos-Sos conjecture, distance related terminology in graphs, relation between the diameter a graph and its complement, Center of a tree. (From Section 2.1)
• Tuesday, 9/30 : Center of a tree, Wiener index and its minimization and maximization for trees and general graphs, Counting spanning trees in a graph. (From Sections 2.1 and 2.2)
• Thursday, 10/2 : Exam #1.
• Tuesday, 10/7 : 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. (From Section 2.3)
• Thursday, 10/9 : Discussion of HW#5 problem1. Weighted graphs, Minimum spanning tree and Kruskal's algorithm, Shortest distances and Djikstra's algorithm. (From Section 2.3)
• Tuesday, 10/14 : The 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,. Discussions of Exam#1. (From Sections 2.3 and 3.1)
• Thursday, 10/16 : Discussion of Exam#1 (contd.). Hall's condition and 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. (From Section 3.1)
• Tuesday, 10/21 : Proofs of min-max relations stated above, Proof of Gallai's Theorem (note the proof technique) for relation between matching and edge cover, k-factors, odd components and Tutte's condition for 1-factors, Berge-Tutte formula for size of maximum matching. (From Sections 3.1 and 3.3)
• Thursday, 10/23 : Parity and no 1-factor when n(G) is even, 1-factor in a 3-regular graph, even-regular graph has a 2-factor and its proof using Hall's Theorem, Vertex-connectivity of a graph, difference between k-connected and connectivity = k. (From Sections 3.3 and 4.1)
• Tuesday, 10/28 : Discussion of some concepts for Exam#2. Connectivity of complete bipartite graphs and d-dimensional hypercubes, Minimum number of edges in a k-connected graph on n vertices and Harary graphs. (From Section 4.1)
• Thursday, 10/30 : Exam #2.
• Tuesday, 11/4 : 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. (From Section 4.1 and 4.2)
• Thursday, 11/6 : Discussion of a problem on Tutte's Condition from HW#8. Proof of Equivalent structural properties of 2-connected graphs, Expansion Lemma, Ear and Closed ear decompositions and how they characterize 2-connected and 2-edge-connected graphs. A characterization of 2-connected graphs in terms of internally disjoint paths, 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. (From Sections 4.1 and 4.2)
• Tuesday, 11/11 : 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.
  Discussion of solutions and grades of Exam#2. (From Section 4.2)
• Thursday, 11/13 : Discussion of solutions of Exam#2. Discussion of some HW#9 problems. Discussion of courses offered next semester.
  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. (From Section 5.1)
• Tuesday, 11/18 : 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), Upper bound using length of directed path. (From Section 5.1)
• Thursday, 11/20 : Discussion of some HW#10 problems. 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, Mycielski's construction of triangle-free graphs with arbitrarily high chromatic number, Intersection graphs, Interval graphs and their chromatic number. (From Sections 7.1 and 5.2)
• Tuesday, 11/25 : Interval graphs and their chromatic number (through greedy coloring), Cartesian product of graphs and their chromatic number, 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, Dirac's Theorem that 4-chromatic graph contains a subdivision of K_4. (From Sections 5.1 and 5.2)
• Tuesday, 12/2 : Mid-term Exam #3.
• Thursday, 12/4 : Discussion of Mid-term Exam#3. 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, 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, 4-color Theorem for Planar Graphs. (From Sections 6.1, 6.2 and 6.3)

• Mathworld : Graph Theory Dictionary
• Planet Math : Graph Theory
• Glossary of terms in combinatorics


• Dynamic Surveys in Combinatorics
• Combinatorics Information Pages


• Textbooks for alternative points of view and for additional applications:
  
  • Graph Theory with Applications by Bondy and Murty
  • Graph Theory (4th ed.) by R. Diestel
  • Modern Graph Theory, B. Bollobas.
  • Graphs and Applications: An Introductory Approach, J.M.Aldous R.J.Wilson
  • Applied Combinatorics, F.R.Roberts
  • Graph Theory Applications, L.R.Foulds
  • Topics in Intersection Graph Theory, T.A.McKee, F.R.McMorris
  • Graph Theory and Applications, Marshall
  • Bipartite Graphs and their Applications, A.S.Asratian, T.MJ Denley, R.Haggkvist