MAT344H1 Lecture Notes - Lecture 1: Enumerative Combinatorics
Document Summary
Def graph: a graph is a set v of vertices and a set e of edges joining distinct vertices s. t. any two vertices are joined by max 1 edge. Def adjacency: vertices are adjacent if they are connected by an edge. Def path: a sequence of distinct vertices each adjacent to the next. Def connectivity: a graph is connected if any two vertices can be connected by a path, else it is disconnected. Def distance between vertices: the distance between two vertices a and b is the length of the shortest path between a and b. Def directed graph: a graph endorsed with a choice of orientation of each edge. Def path in directed graph: a path in an oriented/directed graph is a path that travels only forward. Def circuit: a path whose endpoint is adjacent to its startpoint.
