Math 454/553 Graph Theory/Discrete Applied Math I
Instructor: Hemanshu Kaul
Office: 125C, Engineering 1
Phone: (312) 567-3128
E-mail: kaul [at] iit.edu
Time: 1:50pm, Tuesday & Thursday.
Place: 239, Stuart Bldg.
Office Hours: 3:15-4:15pm Tuesday and Thursday, and by appointment.\\ Emailed questions are also encouraged.
Problem-Solving Session: 4:30pm-5:30pm Tuesday.
Graduate Teaching Assistant: Jinyu Huang; jhuang14 [at] hawk.iit.edu.
TA Office Hours: 2:30pm-4:30pm Friday, 129, E1 Building.
Also, Chris Mitillos at 2:30-3:30pm Monday, 129, E1 Building.
|Course Information|
|Advice|
|Announcements|
|Examinations|
|Homework|
|Class Log & Handouts|
|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!
What is this course really about? Required reading.
The official course syllabi.
Advice for students:
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 starting to learn 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:
- Tuesday, 11/13 : Note the revised schedule for for HWs and Exams in the next 3 weeks:
HW#11: Assigned on Thursday, 11/15 (based on lectures on 11/13, 11/15, 11/20) and due on Thursday, 11/29 (two weeks later).
Mid-term Exam#3: Based on topics corresponding to HW#8, 9, 10. Originally scheduled for Tuesday, 11/20; now scheduled for Tuesday, 11/27.
HW#12: No such HW. Due to the rearrangement of exam schedule and HW#11 due date, I will have to make HW#11 the last HW (a bit longer than usual HWs).
- Thursday, 9/6 : Dates and Syllabi for Exam #1, Exam #2, Exam #3, and the Final Exam have been announced below.
- Thursday, 9/6 : Dates and Syllabi for Exam #1, Exam #2, Exam #3, and the Final Exam have been announced below.
- Thursday, 8/28 : Note the change in TA information and problem session time
- Thursday, 8/23 : HW#1 has been uploaded below. Also see the accompanying comments file.
- Tuesday, 8/21 : Check this webpage regularly for homework assignments, announcements, etc.
Examinations:
- Exam # 1 : Thursday, September 27th. Topics: All the topics (covered in class and through textbook) corresponding to HW#1 to HW#4.
- Exam # 2 : Thursday, October 25th. Topics: All the topics (covered in class and through textbook) corresponding to HW#5 to HW#7.
- Exam # 3 : Tuesday, November
20th 27th. Topics:All the topics (covered in class and through textbook) corresponding to HW#8 to HW#10.
- Final Exam : Thursday, December 6th, 2pm to 4pm. Topics: All topics studied during the semester.
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/refer to 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 Thursday, 8/30. Solutions distributed in class on 8/30, 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/6. Solutions distributed in class on 9/6, Thursday.
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/13. Solutions distributed in class on 9/13, Thursday.
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, October 16th
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/20. Solutions distributed in class on Thursday, 9/20.
Warm-Up Exercises: Section 1.4 - #1, 2, 4, 5, 8.
Suggested Problems: Section 1.3 - #61. Section 1.4 - #14, 20, 29, 37.
Written Problems: Section 1.3 - #49, #53. Section 1.4 - #19or#20, #23, #25. Section 2.1: #30. [You just need the definition of "Trees" for solving 2.1.30, read it!]
- Homework #5 : Due Thursday, 10/4. Solutions distributed in class on Tuesday, 10/9.
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 1.4 - #36. Section 2.1 - #37. Section 2.1 - #50, #62, #64. Section 2.2 - #15.
- Homework #6 : Due Thursday, 10/11. Solutions distributed in class on Thursday, 10/11.
Warm-Up Exercises: Section 2.2 - #1, 2, 3. Section 2.3 - #1, 2, 3, 5. Section 3.1 - #1, 2, 3, 4, 5, 6, 11.
Suggested Problems: Section 2.2 - #6, 10, 16, 17, 18.
Written Problems: Section 2.2 - #7, #8. Section 2.3 - #7, #10, One of {14, 15}. Section 3.1 - #8.
To solve 3.1.8, you only need to read and understand the definition of "perfect matching" from Section 3.1.
- Homework #7 : Due Thursday, 10/18. Solutions distributed in class on Thursday, 10/18.
Warm-Up Exercises: Section 3.1 - #1, 2, 3, 4, 5, 6, 11. Section 3.3: #1, 2, 3, 4.
Suggested Problems: Section 3.1 - #9, 18, 31, 32, 36, 39, 40, 42.
Written Problems: Section 3.1 - #18, #28, #29, #30, #42. Section 3.3: #7.
Comment: Re-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.
You do NOT need any theory from section 3.3 to solve #3.3.7 just read the definition of 1-factor (essentially the same as perfect matching).
- Special Homework #2 for Math 553 : Due Tuesday, 11/27.
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, 11/1. Solutions distributed in class on Tuesday, 11/6.
Warm-Up Exercises: Section 3.3: #1, 2, 3, 4, 5. Section 4.1: #1, 3, 4, 5.
Suggested Problems: Section 3.3: #10, 11, 26, 9, 19, 22. Section 4.1: # 8, 10, 19.
Written Problems: Section 3.3: #6, one of{#15, #16}, #20, #25. Section 4.1: #20, #23.
- Homework #9 : Due Thursday, 11/8. Solutions distributed in class on Tuesday, 11/13.
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, 19, 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. Conditions - submit at least two problems from each of the two sections, Problem 4.2.28 is compulsory for all students.
- Homework #10 : Due Thursday, 11/15. Solutions distributed in class on Thursday, 11/15.
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, you only need to know the statement of Vizing-Gupta theorem from 7.1 we will discuss it on Thursday.
- Homework #11 : Due Thursday, 11/29.
Note this HW is longer than usual: It has a total of 8 problem choices.
MATH 454 students have to submit 6 problems and MATH 553 students have to submit 7 problems.
Solutions distributed in class on Thursday, 11/29.
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: #25. 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 5.2: #11, #15, #32. Section 6.1: #20, #26, #28. One of {Section 6.2: #7; or Section 6.3: #12}.
Class Log:
- Tuesday, 8/21 : Graph definitions and models - acquaintance relations, complement, Ramsey problem, clique, independent set, job assignments, bipartite graphs and matchings, scheduling, proper coloring and chromatic number. (From Section 1.1)
- Thursday, 8/23 : : Handouts with Course Information and discussion of Course requirements and aim, Advice for doing HW, `What this course is really about'. 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, Different ways of proving isomorphism and non-isomorphism, unlabeled representatives of paths, cycles, complete graphs, complete bipartite graphs. (From Section 1.1)
- Tuesday, 8/28 : isomorphism class through equivalence relation, Decomposition of a graph, self-complementary graphs and decomposition of K_n, Petersen graph - definition, drawings, girth & its proof; u,v-walk, trail and path, Every u,v-walk contains a u,v-path. (From Sections 1.1 and 1.2)
- Thursday, 8/30 : Proof of 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, Odd cycle in odd walk, Characterization of bigraphs. (From Section 1.2)
- Tuesday, 9/4 : Characterization of bigraphs, Union of graphs, Clique as a union of bigraphs, Konigsberg problem and Eulerian circuits, Characterization of Eulerian graphs. (From Section 1.2)
- Thursday, 9/6 : 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,d-dimensional Hypercubes. (From Sections 1.2 and 1.3)
- Tuesday, 9/11 : 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, Mantel's theorem. (From Section 1.3)
- Thursday, 9/13 : 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, Degree sum formula for digraphs, cycle in a digraph, Eulerian digraphs and their characterization. (From Sections 1.3 and 1.4)
- Tuesday, 9/18 : 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/20 : 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/25 : Center of a tree, Wiener index and its minimization and maximization for trees and general graphs, Counting spanning trees in a graph, Cayley's formula and Prufer's code for number of labeled trees on n vertices. (From Sections 2.1 and 2.2)
- Thursday, 9/27 : Exam #1.
- Tuesday, 10/2 : 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, 10/4 : Distribution and discussion of Exam#1 and its solutions. Shortest distances and Djikstra's algorithm. (From Section 2.3)
- Tuesday, 10/9 : 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. (From Sections 2.3 and 3.1)
- Thursday, 10/11 : Symmetric difference of graphs, 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, relation between max matching and min vertex cover - equality for bipartite graphs (Konig-Egervary Theorem). (From Section 3.1)
- Tuesday, 10/16 : 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, Proofs of min-max relations stated above, Proof of Gallai's Theorem (note the proof technique) for relation between matching and edge cover. (From Section 3.1)
- Thursday, 10/18 : 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)
- Tuesday, 10/23 : 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, Relation between connectivity, edge-connectivity, and minimum degree. (From Section 4.1)
- Thursday, 10/25 : Exam #2.
- Tuesday, 10/30 : 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, x,y-cut and internally disjoint x,y-paths, and their min-max relation. (From Section 4.1 and 4.2)
- Thursday, 11/1 : 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)
- Tuesday, 11/6 : Discussion of solutions of Exam#2. 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. 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 Sections 4.1 and 5.1)
- Thursday, 11/9 : , 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), Edge coloring, relation between edge-chromatic number of G and chromatic number of L(G) . (From Sections 5.1 and 7.1)
- Tuesday, 11/13 : 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, Bipartite Graphs are Class 1, Mycielski's construction of triangle-free graphs with arbitrarily high chromatic number. (From Sections 7.1 and 5.2)
- Thursday, 11/15 : 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, Maximum number of edges in an r-colorable graph, Turan graph. (From Sections 5.1 and 5.2)
li>Tuesday, 11/20 : 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, 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. (From Sections 5.2 and 6.1)
- Tuesday, 11/27 : Mid-term Exam #2.
- Thursday, 11/29 : Discussion of Exam#2 solutions. Proofs of - Euler's Theorem and edge bound for planar graphs, 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. (From Sections 6.1, 6.2 and 6.3)
Links for Additional Information:
- 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
HOME