| Lecture | Date | Topic(s) | Comments | Reading | Assignment and Quiz Schedule |
| One | 18 and 20 January | Introduction to Graph Theory | The Party Problem; graphs as models; Vocabulary and Definitions; Mathematica demo | Class Notes and from our textbook: the preface and Chapters A and B | Homework 1 on canvas |
| Two | 25 and 27 January | Vocabulary and Definitions, continued | Points, nodes, vertices, endpoints, loops, multiple edges; Directed, Undirected, and Simple Graphs; Multigraph; Real world examples modelled by Graph Theory; Graph Isomorphism with examples; More vocabulary: degree, adjacencies, neighbors, incidence; Classes of Graphs: complete,... To be continued | Class Notes and from our textbook: the preface and Chapters A and B | For Undergraduates Only: Prerequisite Assessment Quiz Due on Monday by 11:59pm. The quiz is online and can be found on canvas under Course Summary. |
| Three | 1 and 3 February | Review Mathematica by doing the tutorials given in Canvas in the first module; graph classes and some graph gadgets | Graph Classes, continued: bipartite, complete bipartite, n-star, path, simple path, cycle, simple cycle; Degree sequence, special property of sum of degrees of a graph, k-regular graphs; Subgraphs (supergraphs): induced, proper, spanning | Class Notes and Chapters C and D in our text. | Quiz 1 due on Tuesday by 12:30pm on canvas: with your team, open book, open notes, open internet, open friends. You and your team should write up should write up solutions together (your own work!) and hand in one quiz for the entire team. Homework 2 is on canvas |
| Four | 8 and 10 February | More Vocabulary; Special Topic: Graphic Degree Sequences | Connecteness: component, maximal, number of connected components,induced subgraph, distance between two vertices, the Girth of a graph, the Peterson Graph. Proof of correctness of the Havel-Hakimi Algorithm. An open research question. Begin Trees. | Class Notes | |
| Five | 15 and 17 Feb | Special Topics. | Matrices and Graphs: New Gadgets; Trees: Definition and Characterization Theorem; powers of the adjacency matrix of a graph and what the entries mean | Class Notes and Mathematica and Matrix Computations | Quiz 2 due on Tuesday by the end of class on canvas: with your partner, open book, open notes, open internet, open friends. Your and your partner should write up should write up solutions together (your own work!) and hand in one quiz for both of you. Homework 3 is on canvas |
| Six | 22 and 24 Feb | Continue to go through the Mathematica tutorials on Canvas in the first module; | Adjacency Matrix, continued: an algorithm to test connectivity; Trees: Unique path characterization, number of edges in a tree | Class Notes and Sections A and D of our text, and TreeQ, IsomorphicQ, DegreeSequence, and RealizeDegreeSequence | Quiz 3 due on Tuesday by 12:30pm canvas: with your team, open book, open notes, open internet, open friends. Your and your team should write up should write up solutions together (your own work!) and hand in one quiz for the entire team. Homework 4 is on canvas |
| Seven | 1 and 3 March | Trees and Connectivity | Bridges, connectivity and another tree characterization; w(G) versus w(G\e), characterization of bridges; Tree edges are bridges; |E(G)| and and |V(G)| with respect to w(G); Minimum number of edges needed for a graph to be connected; yet another tree characterization theorem (three equivalent statements); Spanning trees and characterization of connected graphs; Special Topic: number of spanning trees by way of deletion and contraction. | Class Notes | |
| Eight | 8 and 10 March | No lecture on Tuesday: concentrate on finishing your midterm. | Tuesday 8th March: Midterm is due on canvas by 12:30pm. With team, open book, open notes, open lecture, open internet, open friends. Be sure to write up your own work and hand in one exam for your team on canvas. | For the midterm, study lecture notes through Theorem 3.14 (Matrix Tree Theorem). Study homeworks and quizzes 1-3, and read relevant sections of the textbook, and do problems from those sections as well. | |
| Nine | 15 and 17 March | Spanning Trees, continued | Cayley's Theorem on the number of spanning trees of a complete graph; Defn of contraction along an edge; Big Problem in Three Parts that leads to a recursive algorithm to count the number of spanning trees of an arbitrary graph; Big Example of how to use Big Problem to count spanning trees; Matrix Tree Theorem (an alternative method for counting spanning trees) | Class notes and Section D again | null | 20 - 26 March | Spring Break | No Classes, No Office Hours | Ten | 29 and 31 March | Special Topic: Optimization by way of finding minimum spanning trees. | Kruskal's Algorithm and Prim's Algorithm for finding minimum spanning trees. Definition of weighted graph. | Class notes and Section E in text |
| Eleven | 5 and 7 April | Chapter 4: Connectivity. | A theorem due to Whitney: a relation among edge connectivity, vertex connectivity, and minimum vertex degree. Begin a new special topic related to connectivity: Building reliable communications networks. Given integers k and n with k smaller than n, first find the minimum number of edges that a k-connected graph on n vertices must have. Next, construct such a graph to show that the edge bound is sharp. | Class notes | Quiz 4 due on Tuesday by 12:30pm canvas: with your partner, open book, open notes, open internet, open friends. Your and your team should write up should write up solutions together (your own work!) and hand in one quiz for the entire team. Homework 5 is on canvas. |
| Twelve | 12 and 14 April | Connectivity continued. Section H: Begin planarity. | Construct a reliable (ie k-connected graph on n vertices) communications network with the fewest number of edges. Menger's Theorem: connectivity from a different point of view. Definition of plane and planar graphs. Euler's formula for a plane embedding of a planar graph. The complete graph on five vertices is not planar. | Class notes (Harary Graphs and more on planarity) | Thirteen | 19 and 21 April | Planarity. | Polyhedral Graphs. Average vertex degree of planar (and hence polyhedral) graphs. Dual of a plane graph. Special Topic: The Platonic Solids. Why there are only five of them (tetrahedron, cube, octahedron, icosahedron, dodecahedron). Characterization of Planar Graphs: Subdivision of a graph. Contraction along an edge, revisited. Contractible edge (one that preserves connectivity). Existence of contractible edges in simple 3-connected graphs. First half (and harder part) of Kuratowski's Theorem: a graph with no subdivision of K5 or K3,3 is planar. | Class notes and knowledge of Mathematica objects TetrahedralGraph, OctahedralGraph, CubicalGraph, DodecahedralGraph, and IcosahedralGraph. | Quiz 5 due on Tuesday 12:30pm on canvas: with your team, open book, open notes, open internet, open friends. Your and your team should write up should write up solutions together (your own work!) and hand in one quiz on canvas for the entire team. Homework 6 is on canvas. |
| Fourteen | 26 and 28 April | Finish Characterization of Planar Graphs. Begin Section K: Coloring Graphs | Other half of Kuratowski's Theorem: Any graph with a subdivision of K5 or K3,3 is not planar. New Topic and Chapter: Graph Coloring (an elegant euphemism for scheduling). Crayola Airlines and Their Big Problem. Graph Model: k-coloring, proper k-coloing, color class, chromatic number. Five immediate facts about the chromatic number of a graph (see class notes). Characterization of graphs with chromatic number 2. Brook's Theorem (proof ommitted, technique to come later). Coloring Maps in the Plane: History of the Four Color Theorem. Proof of the Six Color Theorem. | Class notes for helpful hints on displaying graphs with colored vertices. ChromaticNumber and MinimumVertexColoring will be useful Mathematica commands to know, too. | Quiz 6 due on Tuesday by the end of class on canvas: with your team, open book, open notes, open internet, open friends. You and your partner should write up should write up solutions together (your own work!) and hand in one quiz for your entire team on canvas. |
| Fifteen | 3 and 5 May | Final Exam due on Thursday. | Final Exam is comprehensive. Final Exam due on Canvas on Thursday by 12:30pm. With your team, open book, open notes, open friends, open internet. Write up solutions on your own (your own work!) together with your team. Hand in one exam on canvas for your entire team. | ||
| Sixteen | Week of 9 May | Extra office hours to be determined |