Instructor: Hemanshu Kaul

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

Time: 3:15pm, Tuesday & Thursday.
Place: 220, Stuart Bldg.

Office Hours: Noon-1pm Tuesday and Thursday, walk-ins, and by appointment. Emailed questions are also encouraged.

Problem-Solving Session: 5pm-6pm Tuesday.

• Tuesday, 11/2 : Deadline for HW #9 has been extended. This has changed the submission schedule for HW#10 and HW#11 as well, see below for details. ANd this has also changed the syllabus for Mid-term Exam #2, see below.


• Thursday, 9/9 : Special HW #1 for Math 553 students who are not doing a project has been announced below. Note the submission deadline.
• Thursday, 9/9 : Dates and Syllabi for Exam #1 and Exam #2 have been announced below.
• Thursday, 8/26 : HW#1 has been uploaded below. Also see the accompanying comments file.


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

• Exam # 1 : Thursday, October 14th. Topics: Everything covered in class up to and including the lecture on Tuesday, October 5th. This corresponds to material covered in HW#1 to HW#6.
• Exam # 2 : Tuesday, November 23rd. Topics: Everything covered in class from Thursday, September 30th to Thursday, November 11th (including both days). This corresponds to material covered from the second half of HW#6 to end of HW#10.
• Final Exam : Monday, Dec 6th, 2pm-4pm. Topics: All topics studied during the semester up to 11/30, Tuesday.

• Homework #1 : Due Thursday, 9/2. Solutions distributed in class on 9/2, Thursday.
  Warm-Up Exercises: Section 1.1 - #2, #4, #5, #8, #10, #33.
  Suggested Problems: Section 1.1 - #12, #17, #24, #26.
  Written Problems: Section 1.1 - #3, #21, #22, #29, #31, #35. Condition - you have to attempt at least one of {21, 22} AND at least one of {31, 35}.
  Some comments on HW#1.


• Homework #2 : Due Thursday, 9/9. Solutions distributed in class on 9/14, 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, 22, 28.
  Written Problems: Section 1.1 - #12, 26. Section 1.2 - #20, 26, 31, 33. Condition - you have to attempt at least two of {1.1.26, 1.2.31, 1.2.33}.


• Homework #3 : Due Thursday, 9/16. Solutions distributed in class on Tuesday, 9/21.
  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: Section 1.2 - #39, 42. Section 1.3 - #30+#45(count as one), 32, 40, 44. Condition - you can submit at most one of {1.2.39, 1.2.42}.


• Special Homework #1 for Math 553 : Due Tuesday, 10/19. Extended to Tuesday, 10/25.
  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 #4 : Due Thursday, 9/23. Solutions distributed in class on Thursday, 9/23.
  Warm-Up Exercises: Section 1.4 - #1, 2, 4, 5, 8. Section 2.1 - #1, 4, 6, 7, 9.
  Suggested Problems: Section 1.3 - #61. Section 1.4 - #14, 20, 23, 29, 37. Section 2.1 - # 18, 26, 33 34, 36, 40.
  Written Problems: Section 1.3 - #49, 53. Section 1.4 - #25, 36. Section 2.1 - #30, 37. Condition - submit at least one problem from each of the three sections.


• Homework #5 : Due Thursday, 9/30. Solutions distributed in class on Thursday, 9/30.
  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: Section 2.1 - # 50, 62, 64. Section 2.2 - # 7, 8, 15. Comment: For 2.2.15 use Proposition 2.2.8; For 2.2.7 use the statement of Cayley's Formula on pg 82; For second proof of 2.2.8 use Prufer correspondence from proof of Cayley's Formula (to be covered in class on Tuesday).


• Homework #6 : Due Thursday, 10/7. Because of the Exam on 10/14, this will be a strict deadline. Solutions distributed in class on Thursday, 10/7.
  Warm-Up Exercises: Section 2.3 - #1, 2, 3, 5. Section 3.1 - #1, 2, 3, 4, 5, 6, 11.
  Suggested Problems: Section 3.1 - #9, 18, 31, 32, 36, 39, 40, 42.
  Written Problems: Section 2.3 - #7, One of {14, 15}. Section 3.1 - #8, 28, 29, 30. Comment: Reading the definition of vertex cover and statement of Konig-Egervary Theorem on Pg. 112 might be useful for solving 3.1.29 and 30. We will discuss these in class on Tuesday.


• Homework #7 : Due Friday, 10/22 in my mailbox by 4pm. Solutions distributed in class on Thursday, 10/28.
  Warm-Up Exercises: Section 3.2: #2. Section 3.3: #1, 2, 3, 4.
  Suggested Problems: Section 3.2: #5bc, 6, 7. Section 3.3: #10, 11, 26.
  Written Problems: Section 3.1: #18, 42. Section 3.2: #5a. Section 3.3: #6, 7, 20. Comment: You do NOT need any theory from section 3.3 to solve the assigned problems from that section, just read the relevant definitions (which we will cover in detail on Tuesday).


• Special Homework #2 for Math 553 : Due Tuesday, 11/30.
  Read pages 87-89 on 'Graceful labeling' and submit 2.2.4&2.2.23.
  Read pages 116-118 on 'Dominating Sets' and submit 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 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 two out of {8.4.21, 8.4.22, 8.4.24}.


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


• Homework #9 : Due Thursday, 11/4. Extended to Tuesday, 11/9. Solutions distributed in class on Thursday, 11/11.
  Warm-Up Exercises: Section 4.1: #1. Section 4.2: #1, 2, 4, 6.
  Suggested Problems: Section 4.1: #8, 14, 25, 27, 28, 29, 35. Section 4.2: #9, 12, 14, 20, 23, 24.
  Written Problems: Section 4.1: #15, 24, 31. Section 4.2: #18, 22, 28. Condition - submit at least two problems from each of the two sections.


• Homework #10 : Due Tuesday, 11/16. Solutions distributed in class on Tuesday, 11/16.
  Warm-Up Exercises: Section 5.1: 1, 3, 4, 5, 7, 12, 14. Section 7.1: #1, 2, 4.
  Suggested Problems: Section 5.1: 21, 22, 34, 35, 38, 39, 42, 47, 48, 50, 51. Section 7.1: #10, 11, 18, 22, 27, 33.
  Written Problems: Section 5.1: #20, 32, 33, 41. Section 7.1: #26, 34. Condition - Do at least one problem from section 7.1.


• Homework #11 : Due Tuesday, 11/30. Solutions distributed in class on Tuesday, 11/30.
  Warm-Up Exercises: Section 5.1: #9. Section 5.2: #1, 2, 3, 5.
  Suggested Problems: Section 7.1: #25. Section 5.2: #7, 9, 16, 17, 23, 34, 37, 38, 40.
  Written Problems: Section 5.1: #31. Section 7.1: #24. Section 5.2: #11, 15, 32, 39. Condition- Do at least one of {5.1.31, 7.1.24}.


• Homework #12 : OPTIONAL HW (replaces one of the earlier HW scores). Due Friday, 12/3 before 4:30pm. Strict Deadline! HW#12 solutions to be emailed on 12/3, Friday, since the Final Exam is on Monday, 12/6.
  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, 25. Section 6.2: #5, 10, 12. Section 6.3: #5.
  Written Problems: Section 6.1: #20, 21, 26, 28. Section 6.2: #7. Section 6.3: #12. Condition- At most 3 problems from Section 6.1.

• Tuesday, 8/24 : Discussion of Course requirements and aim. Graph definitions and models - acquaintance relations, complement, 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. (From Section 1.1)
• Thursday, 8/26 : : Handouts with Course Information, Advice for doing HW, `What this course is really about'. Path, cycle, subgraph, connected graph, adjacency and incidence matrices and their properties, degree of a vertex, isomorphism, Different ways of proving isomorphism and non-isomorphism, isomorphism class, unlabeled representatives of paths, cycles, complete graphs, complete bipartite graphs, decomposition of a graph, self-complementary graphs and decomposition of K_n, Petersen graph - definition, drawings. (From Section 1.1)
• Tuesday, 8/31 : 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, induced subgraph, Characterization of cut-edge. (From Section 1.2)
• Thursday, 9/2 : Odd cycle in odd walk, Characterization of bigraphs, Union of graphs, Clique as a union of bigraphs, Konigsberg problem and Eulerian circuits. (From Section 1.2)
• Tuesday, 9/7 : Characterization of Eulerian graphs, Degree bounds and existence of paths and cycles through proofs by extremality, Even graphs decompose into cycles, 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. (From Sections 1.2 and 1.3)
• Thursday, 9/9 : d-dimensional Hypercubes, Some properties of hypercubes, 6-cycles in Petersen graph (read the example), 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. (From Section 1.3)
• Tuesday, 9/14 : Mantel's theorem, Induction trap, Degree sequences and their characterization, Graphic sequences and their characterization (Havel-Hakimi Theorem). (From Sections 1.3 and 1.4)
• Thursday, 9/16 : Directed graphs and related terminology and concepts, Degree sum formula for digraphs, cycle in a digraph, 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)
• Tuesday, 9/21 : 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)
• Thursday, 9/23 : 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)
• Tuesday, 9/28 : 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, Weighted graphs, Minimum spanning tree and Kruskal's algorithm. (From Sections 2.2 and 2.3)
• Thursday, 9/30 : Shortest distances and Djikstra's algorithm, Analysis of Djikstra's algorithm, 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, Symmetric difference of graphs, Components of symmetric difference of two matchings, Characterization of maximum matching in terms of non-existence of augmenting paths. (From Sections 2.3 and 3.1)
• Tuesday, 10/5 : 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]. (From Section 3.1)
• Thursday, 10/7 : Relation between vertex cover and independent sets, relation between edge cover and matchings, Proofs of min-max relations stated above, Proof of Gallai's Theorem (note the proof technique) for relation between matching and edge cover, Augmenting Path algorithm for unweighted bipartite graphs. (From Sections 3.2 and 3.3)
• Tuesday, 10/12 : Running time of Augmenting Path Algo, Transversal, Assignment Problem, Weighted cover problem, Duality of these two problems, Equality subgraph and it perfect matching, Hungarian Algorithm for Weighted Bipartite Matching - description and example. (From Section 3.2)
• Thursday, 10/14 : Exam #1.
• Tuesday, 10/19 : k-factors, odd components and Tutte's condition for 1-factors, 'maximal counterexample' for Tutte's Theorem, Proof of Tutte's Theorem, Parity and no 1-factor when n(G) is even, Berge-Tutte formula for size of maximum matching, 1-factor in a 3-regular graph, even-regular graph has a 2-factor and its proof using Hall's Theorem. (From Section 3.3)
• Thursday, 10/21 : Discussion of Exam #1 solutions and score distribution. Completion of the proof of Tutte's Thm, Vertex-connectivity of a graph, difference between k-connected and connectivity = k, connectivity of complete bipartite graphs and d-dimensional hypercubes. (From Section 4.1)
• Tuesday, 10/26 : Completion of the discussion of Exam #1 solutions. 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. (From Section 4.1)
• Thursday, 10/28 : 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, a characterization of 2-connected graphs in terms of internally disjoint paths, Equivalent structural properties of 2-connected graphs, Menger's Local Theorem and Menger's Global Theorem for k-connectivity. (From Section 4.1 and 4.2)
• Tuesday, 11/2 : Proof of Menger's Local 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 edge-connectivity, Menger's Global Theorem for connectivity and edge-connectivity, Proof of Equivalent structural properties of 2-connected graphs, Expansion Lemma. (From Section 4.2)
• Thursday, 11/4 : Overview of Connectivity; Ear and Closed ear decompositions and how they characterize 2-connected and 2-edge-connected graphs. 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. (From Sections 4.1 and 5.1)
• Tuesday, 11/9 : 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). (From Section 5.1)
• Thursday, 11/11 : Edge coloring, relation between edge-chromatic number of G and chromatic number of L(G) and using that to get trivial lower and upper bounds on the edge-chromatic number, 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, Mycielski's construction of triangle-free graphs with arbitrarily high chromatic number. (From Sections 7.1 and 5.2)
• Tuesday, 11/16 : 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. (From Sections 5.1 and 5.2)
• Thursday, 11/18 : 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, Some simple properties of k-critical graphs, Graph drawings, planar graph, and plane graph. (From Sections 5.2 and 6.1)
• Tuesday, 11/23 : Mid-term Exam #2.
• Tuesday, 11/30 : 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 and when its sharp - triangulations and maximal planar graphs, Kuratowski's Theorem characterizing planar graphs (statement only). Distribution of Exam#2 and discussion of the class performance so far. (From Sections 6.1 and 6.3)
• Thursday, 12/2 : Discussion of Exam#2 solutions. Outerplanar graphs - properties, non-examples, How existence of small degree vertex in Trees, Outerplanar graphs, Planar graphs gives an easy bound on their chromatic number, 4-color Theorem for Planar Graphs, [Read from Book: Thomassen's proof of 5-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