MATH 454 Graph Theory and Applications
MATH 553 Discrete Applied Mathematics I
Instructor: Hemanshu
Kaul
Office: 234B, Engineering 1
Phone: (312) 567-3128
E-mail: kaul [at]
math.iit.edu
Time: 1:50pm, Monday and Wednesday.
Place: 122, Engineering 1 Bldg.
Office Hours: 3:30pm-4:30pm Monday and Wednesday, walk-ins, and by appointment. Emailed questions are also encouraged.
Problem-Solving Session: 5pm-6:30pm Mondays.
|Course Information|
|Advice|
|Announcements|
|Examinations|
|Homework|
|Class Log|
|Books|
|Links|
Course Information:
The Course Information Handout has extensive description of the course - topics, textbook, student evaluation policy, as well as other relevant information. Read it carefully!
The official course syllabi.
Advice for students:
What is this course really about? Required reading.
Excellent advice by Doug West on how to write homework solutions in a course like this. Required reading.
Why do we have to learn proofs?
Understanding Mathematics - a study guide
On a more abstract note, here is a discussion of Language and Grammar of Mathematics - which is what you are learning in a course like this.
Excellent advice for math majors, especially those planning to go on to graduate school, by Terry Tao, 2006 Fields medallist. Required reading.
Class Announcements:
- Friday, 12/7 : Math 553 students, there will be no problems from the special HWs in the final exam.
- Friday, 12/7 : Please try the problems from HW#12, even if you are not submitting it.
- Wednesday, 12/5 : Make sure you received and read my email regarding final exam, HWs, etc. sent on Tuesday.
- Wednesday, 11/14 : HW#9 solutions have been distributed through email and are also available outside my office.
- Monday, 11/12 : HW#7 and HW#8 solutions have been distributed through email and are also available outside my office.
- Tuesday, 10/23 : Mid-term Exam #2 has been announced. Look below in the appropriate section.
- Tuesday, 9/18 : Mid-term Exam #1 has been announced. Look below in the appropriate section.
- Monday, 9/10 : HW#1 solutions were distributed in class. Future HW solutions will also be distributed in class or through email.
- Wednesday, 9/5 : The next homework based on the 3 lectures from 9/5, 9/10, and 9/12 will be assigned on Wed 9/12, and will be due a week later. This is being done to avoid any gaps (caused by labor day holiday) in assignment of HW for the rest of the semester.
- Friday, 8/31 : I have added some comments on HW#1 in HW section below.
- Wednesday, 8/29 : A forum for homework discussion is now available on the discussion board in the IIT Blackboard website for this course. You can access blackboard through myIIT or directly at IIT blackboard.
- Wednesday, 8/29 : Read subsections 1.1.27, 1.1.30, 1.1.32, 1.1.33, and 1.1.35 for some definitions and notation needed for HW#1.
- Monday, 8/27 : Due to Labor day holiday next week, the first problem-solving session will be on Wednesday, 9/5 and the first HW will be due on Friday, 9/7.
- Monday, 8/27 : Check this webpage regularly for homework assignments, announcements, etc.
Examinations:
- Exam # 1 : October 15th, Monday at 1:30pm. Topics: Everything covered in class up to and including October 3rd, Wednesday [total 11 lectures].
- Exam # 2 : November 19th, Monday at 1:30pm. Topics: Everything covered in class from and including October 8th, Monday up to and including November 7th, Wednesday [total 10 lectures].
- Final Exam : Thursday, December 13, 10:30am to 12:30pm. Topics: Everything done during the semester, but with slightly greater emphasis on topics covered in the last two HWs. [total 27 lectures, excluding midterm exams].
Homework Assignments:
Words like "construct", "show", "obtain", "determine", etc., typically mean that proof is required. Full credit to most problems requires proof of statements made. Use sentences; you cannot give a proof without words. Results covered in class can be used without proof if you state them correctly.
Warm-Up Exercises: These problems review basic concepts. Think about how to solve them to clarify your understanding of the material before attempting the written problems.
Suggested Problems: If you have time, think about these for extra practice.
Written Problems: Students registered for Math 454 have to submit FOUR out of the SIX problems, while students registered for Math 553 have to submit FIVE out of the SIX problems.
- Homework #1 : Due Friday, 9/7. HW#1 solutions distributed in class on 9/10, Monday.
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 Wednesday, 9/19. HW#2 solutions distributed in class on 9/19, Wednesday.
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 Wednesday, 9/26. HW#3 solutions distributed after class on 9/26, Wednesday.
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 Wednesday, 10/24.
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 Wednesday, 10/3. HW#4 solutions distributed during class on 10/3, Wednesday.
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 out of the two problems from each of the three sections.
- Homework #5 : Due Wednesday, 10/10. Last HW before Mid-term exam#1. HW#5 solutions distributed through email on 10/11, Thursday.
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 (Hint: use Proposition 2.2.8). Condition - submit at least two problems from each of the two sections.
- Homework #6 : Due Friday, 10/26. HW#6 solutions distributed through email on 10/27, Saturday.
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.
- Homework #7 : Due Wednesday, 10/31. HW#7 solutions distributed through email on 11/12, Monday.
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.
- Special Homework #2 for Math 553 : Due Wednesday, 12/5.
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 Wednesday, 11/7. HW#8 solutions distributed through email on 11/12, Monday.
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. Condition - submit at least two problems from each of the two sections.
- Homework #9 : Due Wednesday, 11/14. Last HW before Mid-term Exam#2. HW#9 solutions distributed on 11/14, Wednesday.
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 Wednesday, 11/28. HW#10 solutions emailed on 12/3, Monday.
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 Wednesday, 12/5. HW#11 solutions emailed on 12/7, Friday.
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. Due Monday, 12/10, 5pm. HW#12 solutions to be emailed on 12/10, Monday.
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.
Class Log:
- Monday, 8/27 : Course requirements and aim: Handouts with Course Information, Advice for doing HW, `What this course is really about'. Graph definitions and models - acquaintance relations, complement, clique, independent set. (From Section 1.1)
- Wednesday, 8/29 : Graph definitions and models - 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, subgraph, connected graph, adjacency and incidence matrices and their properties, degree of a vertex, isomorphism. (From Section 1.1)
- Wednesday, 9/5 : 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, girth & its proof; walk, trail and path. (From Sections 1.1 and 1.2)
- Monday, 9/10 : 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)
- Wednesday, 9/12 : 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)
- Monday, 9/17 : 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, k-dimensional hypercube. (From Sections 1.2 and 1.3)
- Wednesday, 9/19 : 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)
- Monday, 9/24 : 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, Degree sum formula for digraphs, cycle in a digraph, Eulerian digraphs and their characterization . (From Sections 1.3 and 1.4)
- Wednesday, 9/28 : 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, Some elementary properties of Spanning trees and trees. (From Sections 1.4 and 2.1)
- Monday, 10/1 : Erdos-Sos conjecture, distance related terminology in graphs, relation between the diameter a graph and its complement, Center of a tree, Wiener index and its minimization and maximization for trees and general graphs. (From Section 2.1)
- Wednesday, 10/3 : 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. (From Section 2.2)
- Monday, 10/8 : 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 with proof, Shortest distances and Djikstra's algorithm. (From Sections 2.2 and 2.3)
- Wednesday, 10/10 : 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)
- Monday, 10/15 : Mid-term Exam #1 at 1:30pm.
- Wednesday, 10/17 : 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)
- Monday, 10/22 : [Guest Lecture by Prof. Michael Pelsmajer] Hungarian Algorithm for Weighted Bipartite Matching - description and correctness. (From Section 3.2)
- Wednesday, 10/24 : Proof of Gallai's Theorem (note the proof technique) for relation between matching and edge cover, Augmenting Path algorithm for unweighted bipartite graphs, k-factors, odd components and Tutte's condition for 1-factors, 'maximal counterexample' for Tutte's Theorem. (From Sections 3.2 and 3.3)
- Monday, 10/29 : 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)
- Wednesday, 10/31 : Vertex- connectivity of a graph, difference between k-connected and connectivity = k, connectivity of complete bipartite graphs and d-dimensional hypercubes, 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. (From Section 4.1)
- Monday, 11/5 : 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)
- Wednesday, 11/7 : A characterization of 2-connected graphs in terms of internally disjoint paths, 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, Menger's Local Theorem and the corresponding dual optimization problems, How to show the optimal value for dual optimization problems using weak duality, Menger's Global Theorem for connectivity and edge-connectivity. (From Section 4.2)
- Monday, 11/12 : Proof of Menger's Theorem, Line graph and the translation of connectivity to edge-connectivity, Proof of Menger's Theorem for edge-connectivity, Menger's Theorem applied to Fan's Lemma. (From Section 4.2)
- Wednesday, 11/14 : Vertex coloring, 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 and the outline of its proof, 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. (From Section 5.1)
- Monday, 11/19 : Mid-term Exam #2 at 1:30pm.
- Wednesday, 11/21 : An upper bound on chromatic number using color-critical subgraph (useful proof idea), An upper bound on chromatic number using length of longest path in an orientation of the graph, 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. (From Sections 5.1 and 7.1)
- Monday, 11/26 : Mycielski's construction of triangle-free graphs with arbitrarily high chromatic number, Interval graphs and their chromatic number (through greedy coloring), Cartesian product of graphs and their chromatic number. (From Sections 5.1 and 5.2)
- Wednesday, 11/28 : Edges in a r-colorable graph, Turan's theorem and its proof, Comments on Erdos-Stone theorem, Hajos conjecture and Hadwiger conjecture, Dirac's Theorem that 4-chromatic graph contains a subdivision of K_4, some simple properties of k-critical graphs. (From Section 5.2)
- Monday, 12/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 and when its sharp - triangulations and maximal planar graphs, outer-planar graphs. (From Section 6.1)
- Wednesday, 12/5 : Kuratowski's Theorem characterizing planar graphs (statement only), 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, Thomassen's proof of 5-color Theorem for planar graphs. (From Sections 6.1, 6.2 and 6.3)
Supplemental Reading (books at Galvin Library):
For alternative points of view and for additional applications:
Graphs and Applications: An Introductory Approach, J.M.Aldous
R.J.Wilson
Applied Combinatorics, F.R.Roberts
Applied Combinatorics, A.Tucker
Graph Theory, R.Diestel
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
Links for Additional Information:
HOME