6.042J Lecture Notes - Lecture 21: Null Graph, Graph Coloring, Complete Graph
13 Apr 2016
School
Course
Professor
Document Summary
We just modify the digraph de nitions using undirected edges instead of directed ones. Walks and paths in simple graphs are essentially the same as digraphs. The length of a walk is the total number of occurrences of edges in it. A walk is a path if all the vertices in the walk are unique. A closed walk is a walk that begins and ends at the same vertex. The length of a walk is one less than the number of occurrences of vertices in it. A single vertex counts as a length zero closed walk as well as a length zero path. A cycle is a closed walk to length three or more whose vertices are distinct expect for the beginning and end vertices. A cycle does not really have a beginning or an end, so it can be described by any of the paths that go around it. Furthermore, cycles in simple graphs do not have a direction.
