Math 332 Graph Theory and Its Applications (Spring 2017)

Home  |  General Information  |  Course plan  |  Homework Assignment

Instructor: Gexin Yu, Jones 127, phone: 221-2040,

Meeting time and location: TR 2-3:20pm Jones Hall 113

Web pages:

Office Hours: TR 10-11am or by appointment. Homework help session every Wednesday 11-11:59am at Jones 131.

Text: (for reference)

Course goal: This is an introductory course about graph theory and its applications on natural and social sciences. We discuss many famous applications and study graph-theoretic concepts such as paths, Eulerian circuits, trees, distance, matchings, connectivity, network flows, colorings, planarity, and spanning cycles. We will also talk about how to apply graph theory concepts in the analysis of social networks.

This is intended to be a COLL 200 course. It sits in the NQR (the Natural world and Quantitative Reasoning) domain, but contains significant applications and motivations in Cultures, Societies, and the Individual (CSI) domain. At each topic, there is a case study/project/reading component, which requires students to read or work on some related topics in natural or social sciences. Throughout the course, the students will be guided to explore the properties and structures of social networks and at the last two weeks, we will introduce how to model and analyze the social networks. Our reading examples including molecule constitutional isomers and graph isomorphism in chemistry, Nobel Prize laureate’s speech on matching theory and applications in economics, the philosophical significance of Four Color Problem, gene recombination, and how NFL schedule the games et al. Projects includes design Apps to improve the course registration process, design routes for more efficient door-to-door campaign, and model popular social medias, just to name a few.

Tests: there is no mid-term tests.

Final Exam: a comprehensive final exam will be offered on Monday May 8, 2-5pm. Location: Jones Hall 113.

Homework: There will be weekly homework assignments. We cannot emphasize the importance of homework enough. Although understanding material while you read the text or listen to lecture is certainly important, your most important studying will be in completing the homework assignments.

Start homework early and work steadily!

Help Session: A weekly homework help session will be offer every Wednesday 11-11:59am at Jones Hall 131.

Attendance: Regular attendance is critical for your success in this course. I expect your presence at every lecture.

Grading: Your final grade is calculated as follows:

Honor Code: Students will uphold William and Mary's stated honor code as it is written, any infractions will be referred to the Honor Council.

ADA accommodation: William & Mary accommodates students with disabilities in accordance with federal laws and university policy. Any student who feels s/he may need an accommodation based on the impact of a learning, psychiatric, physical, or chronic health diagnosis should contact Student Accessibility Services staff at 757-221-2509 or at to determine if accommodations are warranted and to obtain an official letter of accommodation. For more information, please see