Instructor: Hemanshu Kaul
Office: Rettaliata Engg Cntr 125C.
E-mail: kaul [at] iit.edu

Time: 3:15pm-4:30pm, Monday and Wednesday.
Place: Rettaliata Engg Cntr 124.
Office Hours: Monday and Wednesday at 12pm-1pm. And by appointment in-person or through Zoom (send email).

TA Office Hours: Bahareh Kudarzi, Monday 10-11:30am and Tuesday 12-1:30pm, at RE 129 or through Zoom link at Math Tutoring Center.

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


• Thursday, 1/11 : This webpage will be updated every Thursday unless otherwise announced.


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

• Exam #1 : Wednesday, February 21st. Syllabus: Based on topics, examples, and problems corresponding to HWs #1-#5.
• Exam #2 : Wednesday, April 10th. Syllabus: Based on topics, examples, and problems corresponding to HWs #6-#10.
• Final Exam : Wednesday, May 1st, 10:30am-12:30pm, at RE 124. Syllabus: All topics covered during the semester.

• Week #1 : 2 Lectures.
  
  • Topics and Readings: 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. 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)
    
  • Homework:
    The homework problems listed below are from the course textbook unless otherwise noted.
    Note: Follow the detailed instructions and rules for HWs given in the Course Information Handout and emailed comments.
    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 some of these for extra practice.
    Written Problems: The problems you have to submit for grading.
    
    • Reading HW: Read and understand Examples 1.1.30, 1.1.31, 1.1.33, and 1.1.35 from Section 1.1.
    • 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 for submission [PDF]. Due Wednesday, 1/17, by 11pm in Blackboard. Submit a single PDF file through Blackboard Assignment. Some comments on the HW. HW Solutions distributed in class.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #2 : 1 Lecture and 1 Holiday.
  
  • Topics and Readings: 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)
    See below in the Supplementary Reading for a magazine article on graph isomorphism problem and much more light reading.
    
  • Homework:
    The homework problems listed below are from the course textbook unless otherwise noted.
    Note: Follow the detailed instructions and rules for HWs given in the Course Information Handout and emailed comments.
    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 some of these for extra practice.
    Written Problems: The problems you have to submit for grading.
    
    • Reading HW: Read and understand Definitions 1.1.27 and 1.2.2, and Examples 1.2.3 and 1.2.4.
      [Optional] Read about an exciting development regarding graph isomorphism. See another recent development on the "easier" problem of group isomorphism.
    • 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 for submission [PDF]. Due Wednesday, 1/24, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #3 : 2 Lectures.
  
  • Topics and Readings: 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. 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 Sections 1.1 and 1.2)
    
  • Homework:
    The homework problems listed below are from the course textbook unless otherwise noted.
    Note: Follow the detailed instructions and rules for HWs given in the Course Information Handout and emailed comments.
    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 some of these for extra practice.
    Written Problems: The problems you have to submit for grading.
    
    • Reading HW: Read and understand Definition 1.2.21, Examples 1.2.21 and Theorem 1.2.23..
    • 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 for submission [PDF] . Due Wednesday, 1/31, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #4 : 2 Lectures.
  
  • Topics and Readings: Konigsberg problem and Eulerian circuits, Characterization of Eulerian graphs, Min number of trails for decomposing any graph, Even graphs decompose into cycles. 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. (From Sections 1.2 and 1.3)
    
  • Homework:
    The homework problems listed below are from the course textbook unless otherwise noted.
    Note: Follow the detailed instructions and rules for HWs given in the Course Information Handout and emailed comments.
    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 some of these for extra practice.
    Written Problems: The problems you have to submit for grading.
    
    • Reading HW: Read and understand Example 1.3.10, Proposition 1.3.13, Remark 1.3.14, and Proposition 1.3.15.
    • 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 for submission [PDF] . Due Wednesday, 2/7, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #5 : 2 Lectures.
  
  • Topics and Readings: Extremal problems and the structure of their proofs, min number of edges in a connected graph, Mantel's theorem. Smallest minimum degree that implies connectedness, MAX-CUT and analysis of the local switching algorithm. 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)
    
  • Homework:
    The homework problems listed below are from the course textbook unless otherwise noted.
    Note: Follow the detailed instructions and rules for HWs given in the Course Information Handout and emailed comments.
    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 some of these for extra practice.
    Written Problems: The problems you have to submit for grading.
    
    • Reading HW: Read and understand Example 1.3.20.
      Read and understand Example 1.3.24, and Remark 1.3.25.
      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.
    • 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 for submission [PDF] . Due Thursday, 2/15, by 11am in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Weeks #6 and #7 : 3 Lectures and 1 mid-term Exam.
  
  • Topics and Readings: 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 - how to convert one spanning tree into another, Local Search Algorithms over graphs of solutions, Erdos-Sos conjecture and related result, Distance related terminology in graphs, Relation between the diameter a graph and its complement, Center of a tree. Review for Exam. (From Sections 1.4, 2.1 and 2.2)
    
  • Homework:
    The homework problems listed below are from the course textbook unless otherwise noted.
    Note: Follow the detailed instructions and rules for HWs given in the Course Information Handout and emailed comments.
    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 some of these for extra practice.
    Written Problems: The problems you have to submit for grading.
    
    • Reading HW: [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.
    • 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 for submission [PDF] . Due Wednesday, 2/28, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #8 : 2 Lectures.
  
  • Topics and Readings: Wiener index and its minimization and maximization for trees and general graphs, Counting spanning trees in a graph - edge contraction and a recursive formula. 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.1, 2.2, and 2.3)
    
  • Homework:
    The homework problems listed below are from the course textbook unless otherwise noted.
    Note: Follow the detailed instructions and rules for HWs given in the Course Information Handout and emailed comments.
    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 some of these for extra practice.
    Written Problems: The problems you have to submit for grading.
    
    • Reading HW: Read and understand Algorithm 2.3.1 and its Example 2.3.2. We will finish discussing it in class next week.
    • Warm-Up Exercises: Section 2.2 - #1, 2, 3. 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 for submission [PDF] . Due Wednesday, 3/6, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Weeks #9 and #10 : 2 Lectures and 2 Spring Break holidays.
  
  • Topics and Readings: Discussion of Exam 1 grades, score distribution, and solutions.
    Weighted graphs, Minimum spanning tree and Kruskal's algorithm, Shortest distances and Djikstra's algorithm. 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. (From Sections 2.3 and 3.1)
    
  • Homework:
    The homework problems listed below are from the course textbook unless otherwise noted.
    Note: Follow the detailed instructions and rules for HWs given in the Course Information Handout and emailed comments.
    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 some of these for extra practice.
    Written Problems: The problems you have to submit for grading.
    
    • Reading HW: Read Definition 3.1.7 and Example 3.1.8.
      Read the statements of Theorem 3.1.11 and Corollary 3.1.13. We will discuss the proofs in class.
      [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.
    • 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 for submission [PDF] . Due Wednesday, 3/20, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #11 : 2 Lectures.
  
  • Topics and Readings: 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 [Gallai's Theorem]. k-factors, odd components and Tutte's condition for 1-factors (no proof). 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)
    
  • Homework:
    The homework problems listed below are from the course textbook unless otherwise noted.
    Note: Follow the detailed instructions and rules for HWs given in the Course Information Handout and emailed comments.
    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 some of these for extra practice.
    Written Problems: The problems you have to submit for grading.
    
    • Reading HW: Read Example 4.1.3.
      Read and make a note of Remark 4.1.6.
      [Optional] A couple of interesting articles that showed up in my newsfeed this week:
      Is graph theory the key to understanding the brain?
      Talk like a graph: Encoding graphs for large language models, the latest from Google AI research.
    • 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 for submission [PDF] . Due Wednesday, 3/27, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #12 : 2 Lectures.
  
  • Topics and Readings: (Completion of) Connectivity of 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, 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. To be completed next week: 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.)
    
  • Homework:
    The homework problems listed below are from the course textbook unless otherwise noted.
    Note: Follow the detailed instructions and rules for HWs given in the Course Information Handout and emailed comments.
    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 some of these for extra practice.
    Written Problems: The problems you have to submit for grading.
    
    • Reading HW: Read the proof of Theorem 4.2.2.
      Read the proof of Expansion Lemma 4.2.3.
      Read Example 4.2.16.
    • 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 for submission [PDF] . Due Thursday, 4/4, by 11am in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions distributed in class.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #13 and #14 : 3 Lectures and 1 Mid-term Exam.
  
  • Topics and Readings: Completion of the discussion and proofs related to Menger's theorems and related concepts.
    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.)
    
  • Homework:
    The homework problems listed below are from the course textbook unless otherwise noted.
    Note: Follow the detailed instructions and rules for HWs given in the Course Information Handout and emailed comments.
    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 some of these for extra practice.
    Written Problems: The problems you have to submit for grading.
    
    • Reading HW: [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: Basic introduction to the problem and Overview of the construction of the improved lower bound.
      
    • 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 for submission [PDF] . Due Wednesday, 4/17, by 11:59pm in Blackboard. Submit a single PDF file through Blackboard Assignment. HW Solutions to be distributed in class.
      Ask for help during the instructor and TA office hours, or through email to the instructor.


• Week #15 and #16 : 4 Lectures.
  
  • Topics and Readings: Completion of discussion of - Intersection graphs, Interval graphs and their chromatic number (through greedy coloring), Cartesian Product of graphs and their chromatic number. Bipartite Graphs are Class 1.
    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.
    Discussion of Exam#2 scores and problems.
    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. Four and Five color theorems for Planar graphs. (From Sections 5.2, 6.1, 6.2 and 6.3; and elsewhere).
  • Homework:
    The homework problems listed below are from the course textbook unless otherwise noted.
    Note: Follow the detailed instructions and rules for HWs given in the Course Information Handout and emailed comments.
    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 some of these for extra practice.
    Written Problems: The problems you have to submit for grading.
    
    • Reading HW: [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).
      [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
      
    • 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: Homework #12 for submission: 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.. [Optional to submit; replaces one previous lower HW score] Due Friday, 4/26, by 11pm in Blackboard. Submit a PDF file through Blackboard Assignment.
      Ask for help during the instructor and TA office hours, or through email to the instructor.

• There are many articles related to Graph Theory in the excellent magazine Quanta. Notice the variety of topics across mathematics, computer science, physics, and sciences, where graph theory shows up.
• Read about an exciting development regarding graph isomorphism. See another recent development on the "easier" problem of group isomorphism.
• 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.
• Is graph theory the key to understanding the brain?
• Talk like a graph: Encoding graphs for large language models, the latest from Google AI research.
• 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: Basic introduction to the problem and Overview of the construction of the improved lower bound.
• 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).
• 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

• 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

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


• House of graphs


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