Middlebury

MATH 0247

Graph Theory

Graph Theory
A graph (or network) is a useful mathematical model when studying a set of discrete objects and the relationships among them. We often represent an object with a vertex (node) and a relation between a pair with an edge (line). With the graph in hand, we then ask questions, such as: Is it connected? Can one traverse each edge precisely once and return to a starting vertex? For a fixed k/, is it possible to “color” the vertices using /k colors so that no two vertices that share an edge receive the same color? More formally, we study the following topics: trees, distance, degree sequences, matchings, connectivity, coloring, and planarity. Proof writing is emphasized. (MATH 0122 or by waiver) 3 hrs. lect./disc.
Subject:
Mathematics
Department:
Mathematics
Division:
Natural Sciences
Requirements Fulfilled:
DED
Equivalent Courses:

Sections in Spring 2004

Spring 2004

MATH0247A-S04 Lecture (Peterson)