| 1. Graph Basics | What is a Graph? | Definition of a graph, ordered pair (V, E), vertices, edges, simple graphs, directed graphs, order, and size of a graph. | 1 |
| Examples of Graph | Undirected graph, ends of the edge, adjacent neighbors, disconnected graph. | 1 |
| Families of Graph | Complete graph, simple graph, edge between every pair of vertices. | 1 |
| Empty Graph | Definition, empty graph on 4 vertices. | 2 |
| Bipartite Graph | Definition, complete bipartite graph, star graph. | 2 |
| Path | Definition of a path, sequence. | 2 |
| Cycle Graph | Definition of a cycle, cyclic sequence, triangle. | 2 |
| Connected Graph | Definition, path between distinct vertices. | 2 |
| Disconnected Graph | Examples of connected and disconnected graphs. | 3 |
| Regular Graph | Neighborhood of a graph, open neighborhood, closed neighborhood, degree of a vertex, k-regular, cycles, paths, cubic, min-degree, max-degree. | 3 |
| Theorem 1 | The sum of the degrees is twice the number of edges. | 3 |
| 2. Graph Theory Proofs | Corollary | In any graph, there are an even number of odd-degree vertices. | 4 |
| Representing Graphs using matrices | Adjacency matrix, incidence matrix, row sum, column sum. | 4, 5 |
| Problem Set | Simple graph, equality, notations, prove every path is bipartite. | 5 |
| Theorem | Proof that every edge of Pn is of the form Vivi+1. | 6 |
| Corollary | For k=0,1,2 characterize the K-regular graphs. | 6 |
| Theorem | Let G be a bipartite graph with partite sets X and Y, prove that the sum of degrees of vertices in X equals the sum of degrees of vertices in Y. | 6 |
| True/False | If u,v,w ∈ V(G) and there is an even length path from u to w and there is an even length path from v to w then there is an even length path from u to w. | 7 |
| Isomorphisms | Two simple graphs G and H are isomorphic if there is a bijection, notations. | 7 |
| Isomorphic or not? | Same # of vertices, same # of edges, structural similarities or differences, bijection. | 8 |
| 3. Subgraphs | Neighbors of a vertex | Definition, examples. | 9 |
| Spanning and Induced Subgraphs | Subgraphs, vertex deletion, edge deletion, induced subgraph, spanning subgraph. | 9 |
| Theorem | If F is a subgraph of G, Spanning Subgraph, Induced Subgraph. | 10 |
| Theorem | Let G be a graph in which all vertices have a degree of at least 2. Then G contains a cycle. | 10 |
| 4. Graph Isomorphism Problems | Problems | Are the following pairs of graphs isomorphic or not? If they are, give the isomorphism. If not, explain why. | 11 |
| Theorem | Show that any isomorphism between 2 graphs maps each vertex to a vertex of the same degree. | 12 |
| 5. Bipartite Graphs | Theorem | Prove that Cn is bipartite if n is even. | 13 |
| 6. Mathematical Induction | Principle of mathematical Induction | Let P(n) be a statement involving the integer n. Basis, then the statement is true for all the integers n ≥ 1. | 14 |
| Theorem | Let n ≥ 4 be an even integer. Show that there exists a 3-regular graph of order n. | 14 |
| 7. Walks, Trails, and Paths | Walk Trail and Paths | Definitions, walk in a graph, trail, length of the walk. | 15 |
| Path | Path, length of path, closed walk. | 16 |
| Distance between vertices | Definition, length of the shortest path, connected graph. | 16 |
| Theorem | If x,y ∈ V(G) are distinct vertices of G then every x-y walk in G contains an x-y path in G. | 17 |
| Theorem | A graph G is bipartite if it contains no odd cycle. | 17, 18 |
| 8. Shortest Path Problem | The Shortest Path Problem | Edge weighted Graph, weight function, shortest path problem. | 19 |
| Dijkstra’s Algorithm | Algorithm, steps. | 19, 20 |
| 9. Eulerian and Hamiltonian Graphs | Euler Trail and Eulerian Tour | Definitions, theorem for connected graph to be Eulerian. | 21 |
| Theorem | A connected graph has an Euler trail if it has at most 2 vertices of odd degrees. | 22 |
| Decompositions | Definition, edge-disjoint subgraphs, cycle decomposition, path decomposition. | 23 |
| Even Graph | Definition, theorem for a graph to have a cycle decomposition. | 23 |
| Theorem | Proof by induction on the number of edges. | 24 |
| Hamiltonian Graphs | Hamiltonian path, Hamiltonian cycle, conditions for a graph to be Hamiltonian. | 25 |
| Lovasz Conjecture | Every finite connected vertex transitive graph has a Hamilton path. | 25 |
| Automorphism | Definition, similar vertices. | 25 |
| Vertex Transitive Graph | Definition, examples. | 25 |
| Theorem | If G is Hamiltonian, then for every non-empty subset S of V(G), c(G-S) ≤ | 26 |
| Problems | Find a Hamilton path in Peterson Graph. Prove that the Peterson graph has no Hamilton cycle. | 28 |
| Theorem | Show that Km,n is Hamiltonian if n=m ≥ 2. | 29 |
| 10. Bridges and Connectivity | Bridge Edges | Definition, properties, theorem relating to cycles. | 30 |
| Lemma | Let e be a bridge in a connected graph G. Then c(G-e) = 2. | 31 |
| Trees | Definition, acyclic, connected graph, forest. | 31 |
| Corollary | A connected graph is a tree if all of its edges are bridges. | 31 |
| Cayley’s Formula | There are n^(n-2) trees on a vertex set V of n elements. | 31 |
| Theorem | A graph G is a tree if G is acyclic and | 32 |
| Corollary | A forest F of order n with k connected components has m = n - k edges. | 33 |
| Spanning Tree | Definition, properties. | 33 |
| Corollary | Every connected graph has m ≥ n - 1. | 33 |
| Theorem | A graph G is a tree if G is connected and has m = n - 1. | 33 |
| Types of Trees | Path, star, bipartite graph, double star, caterpillar. | 34 |
| Cayley’s Formula | Proof idea, correspondence between labeled trees and Prufer sequences. | 34 |
| 11. Sequences and Series | Degree Sequences of Graphs | Definition, graphical sequence. | 35 |
| Obvious conditions | Sum of degrees must be even, di ≤ n-1. | 36 |
| Theorem (Havel and Hakimi) | Conditions for a sequence to be graphical. | 36 |
| Proof of Havel-Hakimi Theorem | Proof by induction. | 37 |
| Theorem | A sequence d1, d2, …, dn of non-negative integers, n ≥ 2, is a degree sequence of a tree of order n if and only if the sum of di = 2n - 2. | 38 |
| Specific Degrees in Trees | Theorem relating number of vertices of different degrees in a tree. | 39 |
| Theorem | Let T be a tree of order k and G a graph with δ(G) ≥ k-1. Then G contains a subgraph isomorphic to T. | 40 |
| 12. Graph Coloring | Subgraphs of regular graph | Theorem (König): Every graph G with Δ(G) = r is an induced subgraph of an r-regular graph. | 41 |
| Complement of a graph | Definition, self-complementary graph. | 42 |
| Theorem | If a graph is self-complementary, then the number of edges is n(n-1)/4. | 42 |
| Cartesian Product of Graphs | Definition, examples, Euclidean plane. | 43 |
| Hypercube (or n-Cube) | Definition, Hamilton path, Gray code. | 44 |
| Terminology: Maximum vs Maximal | Definitions, examples. | 44 |
| Eccentricity, Radius, and Diameter | Definitions, properties, relation between radius and diameter. | 45, 46 |
| Theorem | Every graph G is the center of some connected graph. | 47 |
| Cut Vertices | Definition, characterization of cut vertices. | 47 |
| Theorem | Every non-trivial connected graph has at least 2 vertices that are not cut vertices. | 48 |
| Bridge | Definition, relation to cycles and paths. | 49 |
| 2-connected Graph | Definition, non-separable or 2-connected. | 49 |
| Block | Definition, maximal non-separable subgraph. | 49 |
| Theorem | If G is a graph with at least 1 cut-vertex, then at least 2 of the blocks of G contain exactly 1 cut-vertex. | 50 |
| Theorem | The center of every connected graph is in a single block. | 50 |
| 13. Planar Graphs | Planar Graph | Definition, plane graph, regions, unbounded region, boundary of a region. | 51 |
| Theorem | Euler’s formula for connected planar graphs: n - m + r = 2. | 52 |
| Corollary | If G is a planar graph with c(G) connected components, then n - m + r = 1 + c(G). | 53 |
| Theorem | If G is a maximal planar graph with n vertices (n ≥ 3) and m edges, then m = 3n - 6. | 53 |
| Corollary | If G is a planar graph with n ≥ 3 vertices and m edges, then m ≤ 3n - 6. | 54 |
| Fact | K5 is not planar. | 54 |
| Lemma | If G is a planar graph with n vertices and m edges and no triangles, then m ≤ 2n - 4. | 54 |
| Fact | K3,3 is not planar. | 55 |
| Sub-division | Definition, elementary subdivision. | 55 |
| Theorem | Any subdivision H of a graph G is planar if G is planar. | 56 |
| Theorem | If a graph G contains a subgraph that is a subdivision of K5 or K3,3, then G is non-planar. | 56 |
| Kuratowski’s Theorem | A graph G is planar if G contains no subgraph which is a subdivision of K5 or K3,3. | 56 |
| Edge Contraction | Definition, operations involved. | 56 |
| Graph Minor | Definition, operations involved. | 56 |
| Theorem (Wagner) | A graph is planar if it has no K5 or K3,3 minor. | 57 |
| Theorem (Kuratowski) | A graph is planar if it has no subgraph that is a subdivision of K5 or K3,3. | 57 |
| Theorem | Is Peterson graph planar? Proof using Kuratowski’s and Wagner’s theorems. | 57 |
| 14. Vertex Coloring | Vertex Coloring | Definition, proper vertex coloring, k-coloring, k-colorable, chromatic number, k-chromatic. | 58 |
| Theorem | Every tree with at least 2 vertices is 2-chromatic. | 59 |
| Theorem | For every graph G, χ(G) ≤ Δ(G) + 1. | 60 |
| Brooks’ Theorem | If G is a connected simple graph and it is neither an odd cycle nor a complete graph, then χ ≤ Δ. | 61 |
| 15. Concurrency Control | Concurrency Control | Lock-based protocol, timestamping protocol, replication with weak consistency, deadlock handling. | 62 |
| Timestamp Ordering Protocol | Read timestamp, write timestamp, logical timestamp, operations (read and write). | 62 |
| Assigning Transaction IDs Globally | Site address, counter, problems with slow clocks. | 63 |
| Deadlock Handling | Resource Allocation Graph (RAG), Wait-for Graph (WFG), deadlock detection, centralized approach, distributed approach. | 64 |
| 16. Parallel Algorithms | Parallel Algorithms | Parallel architecture and algorithms, parallel algorithm by M.J. Quinn, programming point of view, unary operator, binary operator, postfix evaluation, parallel RAM (PRAM). | 65 |
| 17. NP-Completeness | NP-Hard and NP-Complete | Polynomial time, exponential time, travelling salesman problem, sum of subsets, graph coloring, Hamiltonian cycle, non-deterministic algorithm, P class, NP class. | 68 |
| CNF-Satisfiability | Definition, base problem. | 69 |
| Cook’s Theorem | The Satisfiability problem (SAT) is NP-complete. | 70 |
| 3SAT | Definition, 3-CNF. | 70 |
| Clique - Decision Problem (CDP) | Definition, complete graph, clique, maximal size of clique, decision problem, optimization problem. | 71 |
| 18. Asymptotic Notation | Asymptotic Notation | Big-Oh, Big-Omega, Theta, upper bound, lower bound, average bound. | 72 |
| 19. Graph Applications | Various Graph Problems | Examples and applications of graph theory in different scenarios. | 73, 74, 75 |
| 20. K-Dimensional Trees | K-Dimensional Trees | Definition, binary search tree, space partitioning, 2-dimensional case, algorithm for building a k-d tree, algorithm for searching a k-d tree. | 76, 77, 78 |
| 21. Priority Queues and Heaps | Binomial Heap | Definition, properties, operations (insert, delete-min, meld), decrease-key, deletion from F-heaps. | 79, 80, 81, 82, 83 |
| 22. Matrix Operations | Linear Equations Solver | Solving systems of linear equations, matrix representation, uniqueness of solutions, undetermined system, overdetermined system, LUP decomposition. | 83, 84, 85, 86, 87 |
| 23. Dynamic Programming | Dynamic Programming | Principle, optimal substructure, overlapping subproblems, backward approach, example with stages. | 89, 90, 91, 92, 93 |
