Discrete Structures
Revised: September 2020
Course Description
Graph Theory: planarity, Eulerian, Hamiltonian, colorings, and trees. Enumeration:
permutations, combinations, generating functions, recurrence relations. Additional
topics as determined by Instructor. Prerequisites: MATH 250. Three credit hours.
Student Learning Objectives
- Use graphs to model and solve a variety of problems;
- Identify and prove structural properties possessed by a given graph; and
- Use combinatorial modeling to solve problems in discrete mathematics.
- Be able to analyze and use appropriate algorithms related to graphs and combinatorial
problems.
Text
Sarah-marie belcastro, Discrete Mathematics with Ducks, Second Edition. CRC Press, 2019.
Grading Procedure
Grading procedures and factors influencing course grade are left to the discretion
of individual instructors, subject to general university policy.
Attendance Policy
Attendance policy is left to the discretion of individual instructors, subject to
general university policy.
Course Outline
The topics below should be given roughly equal attention. Their chronological ordering
is left to the instructor’s discretion.
- Elements of Graph Theory
Graphs, applications of graph theory, and graph isomorphisms
- Trees, Algorithms, and Searching
Definition and examples of algorithms. Properties of trees, depth-first and breadth-first
searching, and spanning trees.
- Circuits and Graph Coloring
Euler circuits, Hamiltonian cycles, graph coloring, coloring theorems, planarity.
- Counting Methods
Basic counting principles, arrangements and selections, arrangements and selections
with repetition, distributions, and binomial coefficients. Counting with Venn diagrams
and the inclusion-exclusion formula.
- Recurrence Relations and Generating Functions
Generating function models, and calculating coefficients of generating functions.
Recurrence Relation models, divide-and-conquer relations, and solutions of linear
recurrence relations.
- Additional Topics
To be chosen based on instructor expertise and student interest. Examples include:
hypergraphs, mathematics of cryptography, number theory, bijective proofs, review
of induction, the use of computers in discrete mathematics, etc.