Basic Concepts: Graphs and digraphs, incidence and adjacency matrices, isomorphism, the automorphism group;
Trees: Equivalent definitions of trees and forests, Cayleys formula, the Matrix-Tree theorem, minimum spanning trees;
Connectivity: Cut vertices, cut edges, bonds, the cycle space and the bond space, blocks, Menger's theorem;
Paths and Cycles: Euler tours, Hamilton paths and cycles, theorems of Dirac, Ore, Bondy and Chvatal, girth, circumference, the Chinese Postman Problem, the Travelling Salesman problem, diameter and maximum degree, shortest paths;
Matchings: Berge's Theorem, perfect matchings, Hall's theorem, Tutte's theorem, Konig's theorem, Petersen's theorem, algorithms for matching and weighted matching (in both bipartite and general graphs), factors of graphs (decompositions of the complete graph), Tutte's f-factor theorem;
Extremal problems: Independent sets and covering numbers, Turan's theorem, Ramsey theorems;
Colorings: Brook's theorem, the greedy algorithm, the Welsh-Powell bound, critical graphs, chromatic polynomials, girth and chromatic number, Vizing's theorem;
Graphs on surfaces: Planar graphs, duality, Euler's formula, Kuratowski's theorem, toroidal graphs, 2-cell embeddings, graphs on other surfaces;
Directed graphs: Tournaments, directed paths and cycles, connectivity and strongly connected digraphs, branchings;
Networks and flows: Flow cuts, Max flow min cut theorems, perfect square;
Selected topics: Dominating sets, the reconstruction problem, intersection graphs, perfect graphs, random graphs.
| 02.08.2023 | Introduction to basic terminologies; Definition of Graphs, Graph representation; Graph isomorphism; Paths, Cycles; Bipartite graphs; Necessary and sufficient condition for the existence of an Eulerian Tour in a graph |
| 03.08.2023 | Introduction to (i) matchings, (ii) planar embeddings of some classes of graphs, (iii) chromatic number, (iv) Eulerian and Hamiltonian cycles |
| 04.08.2023 | Petersen Graph; Hall's condition : A bipartite graph G[X,Y] has a matching that saturates X ⇔ ∀S⊆ X : |N(S)| ⩾ |S|; Corollary : A bipartite has a perfect matching ⇔ |X| = |Y| and ∀S⊆ X : |N(S)| ⩾ |S|, Every regular non-empty bi-partite graph has a 1-factor or perfect matching(Use Hall's theorem towards a direct proof), Statement of Tutte's theorem[1947]; Examples of Interval graphs; Relationship between chromatic number and clique number for spacial classes of graphs; Problems : Count the number of 5-cycles in Petersen graph; Show that if the girth of a graph G is 5 and δ(G) = k, then show that |V(G)| ⩾ k2 + 1; Given two graphs when do we say that they are isomorphic or identical; Mantel's theorem[1907] : The max #edges in an n-vertex triangle-free simple graph is ⌊n2 / 4⌋ |
| 09.08.2023 | Count the number of C4’s in K3,3; Why does the Petersen Graph have no triangle? Counting the number of 5-cycles and 6-cycles in the Petersen Graph; Definitions of Chordal graphs; Drawing all the possible induced subgraphs of the ‘Kite’; Definition of Perfect graphs; A graph with |E| edges has at least |V| - |E| connected components. |
| 10.08.2023 | Definition of a Stable set, Vertex cover; Vertex covers and stable sets are complementary; Bounding the number of edges using α(G) and β(G) for triangle-free graphs; Graphs with small sized maximum matchings; vertex covers and maximum matchings; 2-factor approximation for vertex covering; |
| 11.08.2023 | Solutions/hints for the problems given in Tutorial 1 and Homework 1; |
| 23.08.2023 | Vertex covers, edge covers; the product α(G)ω(G) for Petersen, bipartite, complements of bipartite, complete, cycle and other simple graphs, verifying that such products are at least as large as the number of vertices in perfect graph examples; Gallai's Theorem; maximal and maximum matchings; augmenting paths, alternating paths; symmetric difference of two matchings; |
| 24.08.2023 | Perfect matchings in general simple connected graphs; Petersen graph is not bipartite, It has a perfect matching and a minimum edge cover of the same size 5; Example of a connected graph with an even number 20 of vertices but a maximum matching of size only 9; Illustration of Tutte's condition for paw, claw, kite, K3,3, triangle, K5, K2.4; Dense graph that are maximal perfect matching deficient; bad sets give such dense graphs; dense graphs exist for bad sets when there are no perfect matchings. |
| 25.08.23 | Tutte's theorem; Proof of Hall's theorem; Proof of Berge's theorem; Proof of Gallai's theorem; application of Tutte's theorem |
| 30.08.2023 | Circles and pair-wise common tangents between circles, of K2,4 and no K2,5 in circle-tangent incident graphs; definition of dominating set; k-regular graphs of girth four; bounds on the chromatic number of a graph; Prove that every n-vertex graph with minimum degree k has a dominating set of size at most n((1 + ln(k+1))⁄(k+1)) |
| 06.09.2023 | Large number of edges lead to subgraphs with proportionate minimum vertex degree i.e., an n vertex graph G=(V,E) with |E| ⩾ (c-1)n contains a subgraph H with δ(H) ⩾ c; Extremal results such as spanning subgraphs of high vertex degrees, every graph G has a bipartite spanning subgraph B such that ∀ v ∈ V(G), dB(v) ⩾ dG(v) / 2; perfect matching is a spanning subgraph; In BFS trees of bipartite graphs of large degree, the sets reachable grow rapidly; Extremal results: Mantel's theorem, bounding triangles in a graph, we can show that the number of triangles in any simple graph of n vertices and m edges is at least (4m / 3n)(m - n2 / 4); The maximal graph idea for proving Tutte's theorem; Properties of the universal set of vertices of a maximally saturated graph with no perfect matching. |
| 08.09.2023 | Scribe Note by Anirudh M. |
| 14.09.2023 | Scribe Note by Bhagoti |
| 27.09.2023 | Tightness of the upper bound of the chromatic number χ(G) in terms of maxG′δ(G′) where G′ is any induced subgraph of G and δ(G′) is the minimum degree of a vertex in G′. Enumerating vertices of a graph G like Hn-1 = G ∖ { xn }, Hn-2 = Hn-1 ∖ { xn-1 } = G ∖ { xn, xn-1 }, … where xn is a vertex with deg(xn) ≤ maxG′δ(G′); we can Greedily color vertices in the order of the sequence x1, x2, …, xn; This result can be exploited for non Δ-regular graphs as maxG′δ(G′) ≤ Δ - 1 making χ(G) ≤ Δ; Every graph G with m edges satisfy χ(G) ⩽ 1⁄2 + √(2m + 1⁄4); the least number k such that G has a vertex enumeration in which each vertex is preceded by fewer than k of its neighbours is called the coloring number col(G) of G; So, χ(G) ⩽ col(G) ⩽ maxG′δ(G′) + 1; [Brooks 1941] Let G be a connected graph. If G is neither complete nor an odd cycle, then χ(G) ⩽ Δ(G); A graph G is perfect if and only if |H| ⩽ α(H) · ω(H) ∀ induced subgraphs H ⊆ G. To show that chordal graphs are perfect, we shall first characterize their structure. If G is a graph with induced subgraphs G1, G2 and S, such that G = G1 ∪ G2 and S = G1 ∩ G2, we say that G arises from G1 and G2 by pasting these graphs together along S. A graph is chordal if and only if it can be constructed recursively by pasting along complete subgraphs, starting from complete graphs. Let G be a graph and x ∈ G a vertex, and let G′ be obtained from G by adding a vertex x′ and joining it to x and all the neighbours of x. We say that G′ is obtained from G by expanding the vertex x to an edge xx′. Any graph obtained from a perfect graph by expanding a vertex is again perfect. Show that χ(H) ∈ {ω(H), ω(H) + 1} for every line graph H; Characterize the graphs whose line graphs are perfect. |
| 29.09.2023 | Scribe Note by Trishita Mukherjee |
| 06.10.2023 | Scribe Note by Sukanth E |
| 11.10.2023 | Scribe Note by Anirudh M |
| 12.10.2023 | Generating perfect graphs by extension at vertices with perfect graphs; alternate proof of the Wilf-Szekeres theorem; Some examples of Δ(G), χ(G) and χ′(G) on K4, K5, K1, n. |
| 13.10.2023 | Discussion of the questions in Homework 3; revisiting the proof of the Wilf-Szekeres theorem and repetition of some vertex and edge coloring upper bounds. |
Tutorial-1 - August 11, 2023
Homework-1- August 11, 2023
Homework-2- September 1, 2023
Homework-3- October 16, 2023
Two class tests will be conducted for this course.