Graphs, Connectedness, And Trees

This packet continues where this introduction to graph theory left off.  If you have no previous experience with graph theory, you ought to go over the previous lesson.

Just in case you need a little refresher, the following list gives brief definitions of some of the terms used in this packet:

• path: a set collection of edges leading from one vertex to another
• cycle: a path that leads back to its starting point never having crossed the same edge twice
• connected: a graph is connected when there is a path between any two vertices; if there exist two vertices for which no path can be formed between, the the graph is not connected.
• tree: a connected graph with no cycles
• adjacent: two vertices are called adjacent when they share an edge
• degree: the degree of a vertex is the number of edges with which it is incident