Graph Theory

3 units

Introduction to graph theory including the basic definitions andtheorems and some more advanced topics which drive much currentresearch in graph theory: Ramsey's Theorem, random graph theoryand, if time permits, Szemeredi's regularity lemma. Graphs will bestudied as abstract objects; however graph theory is also of interestto applied mathematicians because graphs are natural models fornetworks (social, electric, ...). Students should know what a proof isand how to produce one. Some informal understanding of probabilitywill be helpful, but students need not have taken a probability course.