v and w are adjacent if (v, w) or equivalently (w, v) is
an edge. The edge (v, w) is incident upon the vertices v and w.
A path is a sequence of vertices
v1, v2,..., vn, such
(vi, vi + 1) is an edge for
i < n. A path is simple if all vertices on it are distinct, except possibly v1 and
vn. The path has length n - 1 and connects v1 and vn.
A graph is connected if every pair of vertices is connected.
A subgraphG' = (V', E') of a graph
G = (V, E) is a graph
E' contains some edges (u, v) of E such that both u and vare in V'
If E' contains all edges
E for which
u, vV', the
subgraph G' is called an induced subgraph.
A connected component of a graph is an induced subgraph which
is connected and which is not a proper subgraph of any other connected
subgraph of G (i.e., maximal connected induced subgraph).
A simple cycle is a simple path of length
connects a vertex to itself.
A graph is cyclic if it contains at least one (simple) cycle.
A free tree is a connected, acyclic graph.
Examples of undirected graphs
Every free tree with n vertices contains exactly n - 1 edges
If we add any edge to a free tree, we get a cycle.