Syllabus for CSCI 4408/5408, Dr. Ellen Gethner

CSCI 4408/5408, Applied Graph Theory (Spring 2020)

Professor Ellen Gethner

Syllabus

automatically updated on 16 January 2020

[ Instructor and Office Hours | Class Time and Room | Textbook and Software and Laptop | Prerequisites | Objectives | Grades and Policies | Schedule| Academic Deadlines | ]

Instructor

Dr. Ellen Gethner
Email: ellen dot gethner at ucdenver dot edu
Office: Lawrence Street Center LW 817
Phone: 303 315 1405
Office hours (drop in or else make an appointment by calling the CS office at 303-315-1408):

Tuesday 11:30am-12:15pm
Tuesday 3:30-5pm
Thursday 11:30-12:15pm
Thursday 3:30-5:00pm

Class Time and Room

Tuesdays and Thursdays 12:30-1:45pm in Lawrence Street Center Room 836

Textbook and Software and Laptop

Textbook:Graph Theory: A Problem Oriented Approach by Daniel Marcus, published by the Mathematical Association of America (MAA). Available at the Auraria book store and many other places-- this year the book will be delayed until January 31st, but the class notes will cover all of the required material until the book comes in.
Software Requirement: All class notes are given as Mathematica notebooks; you can get Mathematica free through the University of Colorado HERE. Be sure to use your official university email address when you work through the steps to get the software.
Laptop Requirement: You must bring your laptop (with Mathematica installed) to class on class lecture days (not needed on Exam and Quiz days).

Other Resources

Introduction to Graph Theory (4th Edition), by Robin J. Wilson; Prentice Hall or Addison Wesley, 1996 (for both undergraduates and graduates for general graph theory information)
Introduction to Graph Theory (2nd Edition), by Douglas B. West, Prentice Hall, 2000 (especially for graduate students as a good resource for projects, and most other things graph theoretic)
Pearls in Graph Theory : A Comprehensive Introduction, by Nora Hartsfield; Dover
Introduction to Graph Theory, by Chartand and Zhang (2005)
Discrete Mathematics with Algorithms by Albertson and Hutchinson (free download)
Online Graph Theory Warmup by Chris Caldwell
Planar Graph Java Applet Game

Prerequisites

CSCI 2511 (Discrete Structures)

Course Objectives

We will begin by acquiring knowledge of the basic tools in Graph Theory (models and representations, basic results on degrees, isomorphism, and connectivity. Then we will move on to more advanced topics such as Trees, Planarity, and Graph Coloring (including the Four Color Theorem), thickness, and games with graphs. If time permits, we will talk about the graph algorithm that is at the heart of Google's success.

Grades and Policies

Assignments and Quizzes: Homework assignments (6) will count toward 40% percent of your grade. You will not hand in homework assignments: each assignment will have an associated in-class quiz (45 minutes), which will be given only once. The lowest score will be dropped.
- Each assigment will have an assortment of straightforward problems as well as challenging problems.
- To prepare for the quizzes, write up your ideas on all of the problems that you have given some thought to, even if you do not believe you have a complete solution.
- Be sure to be neat, write in complete sentences, and do not leave out any steps: clarity of exposition may contribute toward a positive score. Please talk to one another about the assignments, but the write-ups should be done individually so that you are sure to be prepared for the quiz.
Make-up quizzes: None. I will drop your lowest score. There are no exceptions.
Midterm Exam (30% for undergrads, 20% for grads) Given once only during class on Tuesday 10 March.
Final Exam (30% for undergrads, 20% for grads) Given once only during class on Tuesday 5 May.
Research paper presentation and software demonstration (20%) for graduate students only. A 60 minutes (depending on the size of our class) research presentation to be given to your colleagues in class. Early in the semester I will hand out a list of research papers from which you may choose a paper to present. You are expected to read and thoroughly understand the paper and the contents of the bibliography. In addition you will implement the ideas about which you have learned.You will prepare and present a conference-style presentation on your paper, complete with citations and a software demonstration at the end of the semester. A guide will be posted with the list of possible papers with more explanation.

Schedule

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