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.