Instructor: Hemanshu Kaul

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

Time: 1:50pm, Tuesday & Thursday
Place: 106, Rettaliata Engg Center

Office Hours: 3:05pm-4pm Tuesday, and by appointment (send email).
Emailed questions are also encouraged.

• Thursday, 9/20 : Note the tentative EXAM dates below.


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

• Mid-term Exam I: October 11th, Thursday. Topics: All topics corresponding to HWs#1,2,3.
• Mid-term Exam II: November 15th, Thursday. Topics: All topics corresponding to HWs#4,5.
• Final Exam : December 5th, Wednesday, 10:30am. Topics: All topics studied during the semester.

• Homework #1 [Double HW]: Due Thursday, 9/6 Solutions distributed on Thursday, 9/6.
  
• Homework #2: Due Thursday, 9/20 Solutions distributed on Thursday, 9/20.
  
• Homework #3 [Long HW]: Due Thursday, 10/4 Solutions distributed on Thursday, 10/4.
  
• Homework #4: Due Tuesday, 10/23 Solutions distributed on Thursday, 10/25.
  
• Homework #5 [Double HW]: Due Thursday, 11/8 Solutions distributed on Thursday, 11/8.
  
• Homework #6 [Double HW]: Due Thursday, 11/29 Solutions to be distributed on Thursday, 11/29.
  

• Note : All Theorems/ Rules/ Properties/ Corollaries stated in the log below are proved in class unless stated otherwise.
  
  
• Tuesday, 8/21 : Graph definitions, notation, and models: including subgraph vs. induced subgraph, bipartite, complement, etc. [Read Sections 1.1, 1.2 of textbook]
• Thursday, 8/23 : Graph definitions and models: including Degree-sum formula and its consequences, path, cycle - length, odd/even; Proof by extremality - Every graph contains path of length delta(G), cycle of length delta(G)+1; distance between vertices, girth, diameter, relation between girth and diameter. [Read Sections 1.1, 1.2 of textbook]
• Tuesday, 8/28 : Graph definitions and models: connected/disconnected, components, separating set/ vertex cut, connectivity, k-connected, examples, Disconnecting set of edges, edge-cut, k-edge connected, edge connectivity, examples, relation between connectivity, edge-connectivity and minimum degree. [Read Sections 1.1, 1.2, and 1.4 of textbook]
• Thursday, 8/30 : Relation between connectivity, edge-connectivity and minimum degree; Graph definitions and models: including isomorphic and non-isomorphic graphs, Adjacency and Incidence graphs, Directed graphs, Multigraphs, Loops - definitions and basic notation.
• Tuesday, 9/4 : Petersen graph and d-dimensional hypercube, Path vs Trail vs Walk, Every u,v-walk contains a u,v-path, and its consequences, Every closed walk contains an odd cycle (why not even?), characterization of cut-edge, A graph is bipartite iff it has no odd cycle. [Read Section 1.4 of textbook]
• Thursday, 9/6 : A graph is bipartite iff it has no odd cycle, Every graph has bipartite subgraph with atleast half the edges - existential proof and idea for algorithmic proof; Konigsberg bridge problem, Eulerian circuit, Even graph, Characterization of Eulerian graphs. [Read Sections 1.6, 1.8, 1.10 of textbook]
• Tuesday, 9/11 : Characterization of Eulerian graphs - sufficient condition, Decomposition and an even graph decomposes into cycles; Forest, tree, spanning tree, leaf, existence and removal of leafs, 4 equivalent definitions of tree and related proof techniques, Weighted Graph, Minimum Spanning Tree problem, Kruskal's Algorithm (Greedy Algorithms), Djikstra's Algorithm and BFS tree. [Read Section 1.5 of textbook up to Corollary 1.5.4]
• Thursday, 9/13 : How to change one spanning tree into another by exchanging one edge at a time. Matching in a graph - saturated and unsaturated vertices, perfect matching, Perfect matchings in cliques and complete bipartite graphs, Even order graph with no perfect matching, Maximum vs. maximal matchings, M-alternating and M-augmenting Paths, Symmetric difference of two matchings, Characterization of Maximum matching using augmenting paths, Matching in bipartite graphs and Hall's theorem.
• Tuesday, 9/18 : Proof of Hall's Theorem and applying Hall's theorem to k-regular bipartite graphs, Vertex cover and its weak duality with matchings, Edge covers, Notation for Max independent set, max matching, min vertex cover and min edge cover, Complementary relation between vertex cover and independent set, Konig-Egervary Theorem and Konig Theorem for bipartite graphs, Gallai Theorem. [Read Section 2.1 of textbook]
• Thursday, 9/20 : Proofs of: Konig-Egervary Theorem and Konig Theorem for bipartite graphs, Gallai Theorem. k-factor, Applying Hall's Theorem to find 2-factor in a even-degree-regular graph, Matchings in General graphs - Tutte's Condition, Modification when |V(G)| is even. [Read Section 2.2 of textbook]
• Tuesday, 9/25 : Tutte-Berge Formula for maximum number of saturated vertices (proof as HW). Applying Tutte's condition to Petersen's 1-factor theorem in bridgeless cubic graph, Proof of Tutte's Theorem and the use of "maximal counterexample".
• Thursday, 9/27 : Quick Review of k-(edge)-connected and (edge-)connectivity. u,v-cut, u,v-connectivity, pairwise internally disjoint u,v-paths, u,v-edgecut, edge-disjoint u,v-paths, Menger's local theorems for vertex and edge connectivity, Menger's global theorem, How to show k(u,v)=lambda(u,v)=t for a given small graph. How to prove the edge connectivity versions of Menger's theorems from vertex connectivity versions - Line graph.
• Tuesday, 10/2 : How to prove the edge connectivity versions of Menger's theorems from vertex connectivity versions - Line graph, edge disjoint u,v-paths, u,v-edge-connectivity. Proof of Menger's vertex connectivity theorem. Expansion lemma. [Read Section 3.3 of textbook]
• Thursday, 10/4 : Drawing of a graph, Planar graph, plane graph, examples and non-examples, faces, how to show K_5 and K_3,3 are nonplanar, dual graph of a plane graph and their inter-relations, examples, length of a face and relation to degree of dual. [Read Section 4.2 of the textbook]
• Tuesday, 10/9 : Euler's formula, Bounding the edge size of a planar graph, Maximal planar graphs and triangulations, Subdivisions and Minors - definitions and examples, Structural description of subdivision and minor, Kuratowski's and Wagners characterizations of planar graphs (no proof).
• Thursday, 10/11 : Mid-term Exam #1.
• Tuesday, 10/16 : Discussion of Mid-term Exam#1. Kuratowski's and Wagners characterizations of planar graphs (no proof), Outerplanar graphs - examples and non-examples, Characterization of Outerplanar graphs (HW), Crossing number, Zarankiewicz conjecture for cr(K_{m,n}), Hill's Conjecture for cr(K_n). [Read Sections 1.7 and 4.6 of the textbook]
• Thursday, 10/18 : Edge bound on crossing number, Crossing lemma using a probabilistic amplification argument. Proper coloring, chromatic number, 4-color theorem (no proof), examples, partition into color classes, lower bounds using clique number and independence number, examples of sharpness and gap.
• Tuesday, 10/23 : Upper bound using greedy coloring, Brook's theorem (proof later), greedy coloring using carefully chosen vertex order, Coloring number as a bound on Chromatic number, Degeneracy argument for bounding chromatic number with examples, Degeneracy form of Coloring number, Degeneracy of trees, Outerplanar graphs, planar grpahs, Coloring trees, outerplanar and planar graphs using a vertex of "small" degree.[Read Sections 5.1 and 5.2 of the textbook]
• Thursday, 10/25 : Proof of Brook's theorem. Edge coloring and edge chromatic number and its relation to chromatic number using line graph, partition into matchings, Vizing-Gupta theorem (without proof) and Class 1 and Class 2 graphs (but edge-chromatic number remains a hard problem). [Read Section 5.3 of the textbook]
• Tuesday, 10/30 : How multigraphs effect the edge-chromatic number - fat triangle and Shannon's (no proof/HW) 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 and their applications, Interval graphs.
• Thursday, 11/1 : Interval graphs and their Chromatic number, Perfect graphs and their examples (Chordal graphs, Comparability graphs, etc.) and properties (Perfect Graph theorem and Strong Perfect graph theorem - no proof). List coloring, List chromatic number - upper and lower bounds, comparison to chromatic number. [Read Section 5.4 of the textbook]
• Tuesday, 11/6 : Arbitrarily high lower bound on list chromatic number of a bipartite graph, Probabilistic method and its application to an upper bound for a complete bipartite graph. List coloring a planar graph and loaded induction. [Read Section 5.4 of the textbook]
• Thursday, 11/8 : Conjectures and methods in list coloring problems. Extremal Graph theory. Mantel and Turan's theorems, Turan graph, ex(n,H) and its contrapositive form. [Read Section 7.1 of the textbook.]
• Tuesday, 11/13 : Erdos-Stone theorem (no proof), Bipartite Turan numbers, Counting argument for ex(n,C_4) and applying Jensen's inequality, Zarankiewicz problem, Kovari-Sos-Turan theorem for z(m,n;s,t) and its counting argument. [Read Section 9.1 of the textbook.]
• Thursday, 11/15 : Mid-term Exam #2.
• Tuesday, 11/20 : Ramsey Problem - upper and lower bound for R(3,3), Two definitions of R(p,q), Graph Ramsey number R(G1, G2,...Gk). Inductive bound on R(p,q), Proof of finiteness of R(p,q) and applying its upper bound based on parity od the summands, Erdos' probabilistic argument for lower bound on R(k,k) and its comparison to the upper bound. [Read Section 9.2 of the textbook.]
• Thursday, 11/22 : Thanksgiving Break.
• Tuesday, 11/27 : Chvatal's theorem for determining R(Tree, K_n), Burr-Erdos-Spencer theorem for determining R(mK_3, mK_3).
• Thursday, 11/29 : Eigenvalues of a graph and application to graph parameters including chromatic number.

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


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


• Textbooks for alternative points of view and for additional applications:
  
  • Graph Theory with Applications by Bondy and Murty
  • Introduction to Graph Theory, 2nd edition, D. West.
  • Modern Graph Theory, B. Bollobas.
  • Graph Theory (2008 edition), Bondy & Murty.
  • Algorithmic graph theory and perfect graphs, 2nd edition Martin Golumbic.
  • Graphs and Applications: An Introductory Approach, J.M.Aldous & R.J.Wilson.
  • Graph Theory Applications, L.R.Foulds.
  • Topics in Intersection Graph Theory, T.A.McKee & F.R.McMorris
  • Bipartite Graphs and their Applications, A.S.Asratian, T.MJ Denley, R.Haggkvist
  
  

  ---