CSCI 4408/5408, Applied Graph Theory (Elective Course) (Spring 2023: ONLINE COURSE)

Professor Ellen Gethner

Syllabus


automatically updated on 7 January 2023

[ Instructor, Office Hours, and Teaching Assistant | Class Time and Room | Textbook and Software Requirements | Prerequisites | Objectives | Grades and Policies | Schedule| Academic Deadlines | Mental Health Resources| ]




Instructor

Dr. Ellen Gethner
Email: ellen dot gethner at ucdenver dot edu
Office: Office hours are on zoom: Tuesdays: 12:30-3pm Wednesdays: 12:30-3pm Make an appointment with the CS office at 303-315-1408 to obtain a time and a zoom link

Teaching Assistant (TA)


Class Time and Room

This is an online and self-paced course Relevant details about assignments, quizzes, and tests (in person, location and times) and their respective due dates are on canvas and on this page.
Click on the
Schedule link for all reading material and due dates. Our Canvas page Course Summary has all due dates, as well.

Textbook and Software Requirements

  1. 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.
  2. Software Requirement: All class notes are given as Mathematica notebooks; you can get Mathematica free through the University of Colorado (use VPN before clicking) HERE. You must use VPN to access this website. Be sure to use your official university email address when you work through the steps to get the software.

Other Resources

  1. 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)
  2. 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)
  3. Pearls in Graph Theory : A Comprehensive Introduction, by Nora Hartsfield; Dover
  4. Introduction to Graph Theory, by Chartand and Zhang (2005)
  5. Discrete Mathematics with Algorithms by Albertson and Hutchinson (free download)
  6. Online Graph Theory Warmup by Chris Caldwell
  7. Planar Graph Java Applet Game

Prerequisites

CSCI 2511 (Discrete Structures)

Course Objectives

ABET Criteria

Grades and Policies

Suggested Self Paced Schedule (Due dates are firm)

Lecture Date Topic(s) Comments Reading Reading Assignments, Quiz, and Test Schedules
One 16 and 18 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 23 and 25 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 Jan 30 and Feb 1 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 Monday by 12:30pm (lunchtime) as an upload on canvas: with your team, open book, open notes, open internet, open friends. You and your team should write up solutions together (your own work!) and hand in one quiz for the entire team. Homework 2 is on canvas
Four 6 and 8 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 13 and 15 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 Monday by 12:30pm as an upload on canvas: with your team, open book, open notes, open internet, open friends. You and your team should write up solutions together (your own work!) and hand in one quiz for your entire team. Homework 3 is on canvas
Six 20 and 22 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 Monday by 12:30pm canvas: with your team, open book, open notes, open internet, open friends. You and your team should write up solutions together (your own work!) and hand in one quiz for the entire team. Homework 4 is on canvas
Seven 27 Feb and 1 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 Grad Student Project Proposal Due on Canvas on Monday
Eight 6 and 8 March Midterm Exam this week on Monday. The Midterm Exam is in person without your team on Monday from 12:30-1:45pm in King 201. You may bring two sheets of 8.5" x 11" paper with notes on both sides. Do not hand in the notes. 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 13 and 15 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 19 - 25 March Spring Break No Classes, No Office Hours
Ten 27 and 29 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 Quiz 4 due on Monday by 12:30pm canvas: with your team, open book, open notes, open internet, open friends. You and your team should write up solutions together (your own work!) and hand in one quiz for the entire team. Homework 5 is on canvas.
Eleven 3 and 5 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 10 and 12 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 due on Monday by 12:30pm on canvas: with your team, open book, open notes, open internet, open friends. You and your team should write up solutions together (your own work!) and upload one quiz on canvas for the entire team. Homework 6 is on canvas.
Thirteen 17 and 19 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 24 and 26 April Finish Characterization of Planar Graphs. Begin Section K: Coloring Graphs; Grad Student Video Presentation upload on Canvas due on Wednesday by 1pm. 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 Monday by 12:30pm as an upload on canvas: with your team, open book, open notes, open internet, open friends. You and your team should write up solutions together (your own work!) and hand in one quiz for your entire team on canvas.
Fifteen 1 and 3 May The final Exam is on Monday, 1 May at 12:30pm-1:45pm in King 201. Final Exam (undergrads only) is comprehensive. The final Exam is in person without your team on Monday at 12:30pm-1:45pm in King 201. You may bring two sheets of 8.5" x 11" paper with notes on both sides. Do not hand in the notes.
Sixteen Week of 8 May Extra office hours to be determined

Mental Health Resources

CU Denver faculty and staff understand the stress and pressure of college life. Students experiencing symptoms of anxiety, depression, substance use, loneliness or other issues affecting their mental well-being, have access to campus support services such as the Student and Community Counseling Center, the Wellness Center and the Office of Case Management. Students also have access to the You@CUDenver on-line well-being platform available 24/7. More information about mental health education and resources can be found at Lynx Central and CU Denver’s Health & Wellness page. Students in imminent crisis can contact Colorado Crisis Services for immediate assistance 24/7 or walk-in to the counseling center during regular business hours.