Some Links:
Some Links:
We will use the term "vertex" and "node" interchangeably.
Defined this way, there can be at most one edge between two vertices since E is a set and can have at most one "copy" of (u,v). Some people call such graphs simple graphs, we will just say "graphs". Graphs that are allowed to have multiple edges between the same pair of vertices will be called multigraphs. In a multigraph, the set of edges E will have to be a multiset.
Since the set of vertices V is required to be a non-empty set, we do not allow a graph with zero vertices. However, a graph with an empty set of edges is allowed.
An edge, either directed or undirected, from a vertex to itself is called a self-loop. We allow graphs to have self-loops unless otherwise specified.
Some Links:
This type of coloring is also called a vertex coloring. Sometimes people consider coloring the edges of a graph. For this class, we'll stick to coloring vertices.
Some links:
Formally, a path is a sequence of edges (u1,v1), (u2,v2), (u3,v3), ..., (un,vn) in a graph such that for all i = 1, ..., n-1, vi = ui+1. I.e., the end point of an edge in the path must the starting point of the next edge in the path.
We say that n is the length of the path. If u1 = vn (i.e., the path ends at its starting point), then the path is called a circuit.
The term "simple" is often used to modify path and circuit. Some people use "simple path" to indicate paths that do not repeat vertices. Others use "simple path" to indicate paths that do not repeat edges. This is too confusing. We will simply say a path that does not repeat a vertex or a path that does not repeat an edge and refrain from using the word "simple".
Some links: