Lecture | Date | Topic(s) | Comments | Reading | Assignment and Quiz Schedule | ||
One | 19 and 21 January 2016 | Introduction to Graph Theory | The Party Problem; graphs as models; Vocabulary and Definitions; Mathematica demo on the 21st | Class Notes and from our textbook: the preface and Chapters A and B | Homework 1 posted (see student webpage) | ||
Two | 26 and 28 January 2016 | 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 | |||
Three | 2 and 4 February 2016 | Mathematica Session on Thursday; 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 on Tuesday; Homework 2 posted (see student webpage) | ||
Four | 9 and 11 February 2015 | 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 | 16 and 18 Feb 2016 | Special Topics. Meet in our regular classroom. | 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 Multiplication | Quiz 2 on Tuesday; Homework 3 posted (see student webpage) | ||
Six | 23 and 25 Feb 2016 | 2nd Mathematica Session on Thursday; | 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 is on Thursday; Homework 4 posted (see student webpage) | ||
Seven | 1 and 3 March 2016 | 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 2016 | Midterm plus Spanning Trees, continued | Tuesday 8th March: Exam One | 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 2016 | 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 | 21-27 March 2016 | Spring Break: no classes |
Ten | 29 and 31 March 2016 | 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 | Quiz 4 on Tuesday; Homework 5 posted (see student webpage) | ||
Eleven | 5 and 7 April 2016 | 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 | Twelve | 12 and 14 April 2016 | 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) | Quiz 5 on Tuesday; Homework 6 posted (see student webpage) |
Thirteen | 19 and 21 April 2016 | 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 ecdges 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. | |||
Fourteen | 26 and 28 April 2016 | 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 on Tuesday | ||
Fifteen | 3 and 5 May 2016 | Exam plus graduate student presentations | Tuesday 3rd May, Exam 2; Graduate Student Presentations on Thursday | Exam 2 is comprehensive. | |||
Sixteen | Week of 9 May 2016 | Graduate Student Presentations during our final exam time if necessary | Extra office hours and graduate student research paper presentations schedule to be determined |