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.

Grading Basis: Graded
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”.

Click here for course scheduling information. | Check course textbook information