Revised: February 2015
Graph Theory: planarity, eulerian, hamiltonian, colorings, and trees. Enumeration:
permutations, combinations, generating functions, recurrence relations, and inclusion-exclusion.
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.
Applied Combinatorics (Fourth Edition), John Wiley & Sons, 2002.
Grading procedures and factors influencing course grade are left to the discretion
of individual instructors, subject to general university policy.
Attendance policy is left to the discretion of individual instructors, subject to
general university policy.
Chapter 1: Elements of Graph Theory (6 days)
All sections: Graph models, graph isomorphisms, edge counting, and planarity.
Chapter 2: Covering Circuits and Graph Coloring (6 days)
All sections: Euler circuits, Hamiltonian cycles, graph coloring, and coloring
Chapter 3: Trees and searching (5 days)
Sections 1 - 2: Properties of trees, depth-first and breadth-first searching,
and spanning trees. Remaining topics may be covered at the instructor's discretion.
Chapter 4: Network Algorithms (Optional, at the instructor's discretion as time allows)
Chapter 5: Counting Methods for Selections and Arrangements (10 days)
Sections 1 - 4, and highlights of section 5: Basic counting principles, arrangements
and selections, arrangements and selections with repetition, distributions, and binomial
Chapter 6: Generating Functions (4 days)
Sections 1 and 2: Generating function models, and calculating coefficients of
Chapter 7: Recurrence Relations (4 days)
Sections 1 - 3: Recurrence Relation models, divide-and-conquer relations, and
solutions of linear recurrence relations.
Chapter 8: Inclusion-Exclusion (4 days)
Sections 1 - 3: Counting with Venn diagrams, the inclusion-exclusion formula,
and rook polynomials (if time allows).