Computer Science

General goals: The student will obtain a broad understanding of the classic results in graph theory as well as an introduction to the primary areas of research in modern graph theory. Specific goals: Fundamental topics which the student will know after the course include: trees and spanning trees in graphs; connectivity in graphs; Hamiltonian cycles and sufficient conditions for their existence. Menger’s theorem and max flow/min cut in graphs. Matching theory in graphs including Konig, Hall, and Tutte’s theorems. Extremal graph theory and Turan’s theorem and Ramsey theory. Planar graphs and graph coloring. Knowledge and understanding: The student will obtain mastery of basic techniques in mathematical proofs and a familiarity with more advanced techniques. The student will acquire knowledge of the fundamental results in the area and how they are proven. Applying knowledge and understanding: The student will learn how to apply mathematical induction in a range of contexts and resolve basic questions in graph theory. Critical and judgmental skills: The student will acquire the critical judgement skills to understand which proof techniques can be applied in which instances, and determine what are the significant open questions in the area. Communication skills: The student will develop the ability to present written rigorous mathematical proofs. Learning ability: Upon completing the course of study, the student will have the necessary tools to read research papers in graph theory and understand the techniques found there. The student will have the tools to begin research projects in graph theory.