University General Course Catalog 2021-2022
Sep 25, 2022
 HELP University General Course Catalog 2021-2022 ARCHIVED CATALOG: LINKS AND CONTENT ARE OUT OF DATE. CHECK WITH YOUR ADVISOR. Print-Friendly Page (opens a new window)

# MATH 485 - Graph Theory & Combinator

(3 units)
Counting rules; generating functions; recurrence relations; inclusion-exclusion; pigeonhole principle; Ramsey theory; fundamental graph theory concepts (connectedness, coloring, planarity); Eulerian/Hamiltonian chains and circuits; matching.

Recommended Preparation: MATH 330 .

Units of Lecture: 3
Offered: Every Fall

Student Learning Outcomes
Upon completion of this course, students will be able to:
1. solve simple and complex counting problems, by using the addition and product rules, recognizing permutation/combinations with and without replacement, rephrasing as occupancy problems, and/or using the inclusion-exclusion principle/derangements.
2. demonstrate an understanding of the concept of computational complexity for algorithms, including the use of “Big O” notation.
3. demonstrate an understanding of the main concepts of graph theory, including graphs versus digraphs, connectedness, graph coloring, planarity, as well as the properties of bipartite graphs, complete graphs, and trees.
4. demonstrate knowledge of some of the great historical problems and results in graph theory/combinatorics, including the four-color problem, the Konigsberg bridge problem, Euler’s formula, the travelling salesman problem, the hatcheck problem, Kuratowski’s theorem, Ramsey’s theorem, and the solution to the Fibonacci recursion.
5. make simple “discrete” arguments/proofs, such as using mathematical induction or making “combinatorial arguments”.