# MATH 310 Syllabus

### Discrete Structures

Revised: February 2015

## Course Description

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.

## Text

Alan Tucker, 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

Attendance policy is left to the discretion of individual instructors, subject to general university policy.

## Course Outline

• 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 theorems.
• 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 coefficients.
• Chapter 6: Generating Functions (4 days)
Sections 1 and 2: Generating function models, and calculating coefficients of generating functions.
• 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).