A cycle is a path with thesame star

A cycle is a path with the
same start and end vertex. That is vstart = vend. A simple path is a path where each
vertex is distinct. Similarly, a simple cycle is a cycle where each vertex is distinct, except
for the start and end vertex. See Figure 3.1 for an example of a simple path and a simple
cycle.
A graph is connected if there exists a path between any pair of vertices. That is, if it is
possible to get from one vertex to any other vertex in the graph. A self loop is an edge
that connects a vertex to itself, that is e = (vi, vi). Such edges will be counted twice in
deg(v). Two distinct edges, say e and e′, are parallel if their endpoints are the same. That
is, if e = (vi, vj) = e′. A graph containing parallel edges is called a multi graph, because E
is a multiset as allowed in the first definition of a graph. A simple graph is an undirected
graph with no self-loops and no parallel edges. By definition of a simple graph, E is a
“real” set as opposed to a multiset. The degree of a vertex in a simple graph is at most
n − 1, and the degree is the same as the number of neighbouring vertices. The graph in
Figure 3.1 is simple and connected. If a graph is not connected, its maximal connected
subgraphs are called connected components.
We will show a lower bound on the number of edges in a simple connected graph by
induction. For the base case, consider a trivial simple connected graph G consisting of
one vertex (n = 1), and thus no edges (m = 0). Hence the expression m = n − 1 = 0
holds. Then inductively consider a simple connected graph with n − 1 vertices where
m = (n − 1) − 1 = n − 2 holds. Adding a new vertex to G requires one edge incident to
the new vertex for the graph to be connected, so m = (n − 2) + 1 = n − 1. This proves
that any simple connected graph with n vertices has m ≥ n − 1 edges. It is easy to see
that connecting a graph to an extra isolated vertex with exactly one edge does not induce
a cycle in the simple connected graph. As the graph is connected and has no cycles, there
exists exactly one simple path between each pair of vertices. Hence, adding one more edge
to the graph will add an extra simple path between some pair(s) of vertices, and thus a
cycle. Hence, a connected simple graph with m = n − 1 has no cycles. By definition a
tree is a connected graph without cycles, equivalent to that m = n − 1. A forest is by
definition the union of a set of one or more vertex disjoint trees.
Another special case of a simple connected graph is the complete graph. A complete graph
is a graph which contains all possible edges, that is, each pair of distinct vertices (vi, vj)
where i 6= j are connected by an edge. Every vertex in a complete graph has degree n−1,
that is one incident edge to every other vertex in the graph. The total number of edges
is the number of distinct vertex pairs: n (n − 1) /2 or equivalently