Graph Theory Conventions
For additional graph theory background see [Tuc07].
graph: A graph consists of a finite set of vertices and a finite set of edges each corresponding to a pair of vertices.
vertices: In Example 1, the vertex set is {1,2,3,4,5}.
edges: In Example 1, the edge set is {{1,2}, {2,4}, {3,4}, {1,3}, {4,5}}
digraph: A digraph is a graph with a direction assigned to each edge.
arc: An arc is an edge assigned a direction.
degree of a vertex: The degree of a vertex is the number of edges that are incident to (coming out of) it. In Example 1, vertex one has degree 2, while vertex four has degree 3.
walk: A walk traverses consecutive edges in a graph (following the direction of the edges in the case of a digraph) allowing repeated edges and vertices.
trail: A trail is a walk that allows repeat vertices but not repeat edges (Ex. 2: 5-6-1-5-4).
path: A path is a walk that does not repeat any vertices (Ex. 2: 8-2-3-9-4).
circuit: A circuit is a closed trail
Example 1: A graph
(Ex. 2: 5-1-3-2-1-6-5).cycle: A cycle is a closed path (Ex. 2: 7-2-8-7).Euler circuit: An Euler circuit is one which traces every single edge.
Eulerian graph: An Eulerian graph is a graph containing an Euler circuit, either a directed graph with equal in-degree and out-degree at each vertex or an undirected graph where the degree of every vertex is even. (See Example 3.)tree: A tree is a connected graph that does not contain any cycles. In some cases there is a designated vertex called a root. (See Example 4.)
leaf: A leaf is a tree vertex with degree one. (The vertices at the bottom of Example 4 are leaves.)
Example 3:
An Eulerian graph
Example 2
complete graph on n vertices (Cn): In the case of a complete graph with n vertices, each vertex is adjacent (connected) to the other n-1 vertices. (See example 5.)
bipartite graph: A bipartite graph can be partitioned into two sets V1 and V2 such that every edge joins a vertex in V1 with a vertex in V2.
complete bipartite graph (Kn,m): A complete bipartite graph is a bipartite graph in which every vertex in V1 (consisting of n vertices) is connected to every vertex in V2 (consisting of m vertices).
Example 4: A tree
Example 5: A complete graph
Example 6: Bipartite Graph
Example 7: Complete bipartite graph K2,3