
Practical Discrete Mathematics
By :

We will start by defining graphs mathematically, along with any other related definitions, before moving on to consider common ideas about trees, networks, and directed graphs.
A graph G has two parts. First, V = {v1, v2, …, vk} is a set of vertices, also known as nodes. Second, E is a set of edges, each of which connects some pairs of nodes. We represent a graph as G = (V, E).
An edge is represented mathematically as a set made up of the two vertices it connects. If there is an edge connecting nodes vi and vj, we will call this edge eij = {vi, vj} and we say it is incident to vertices vi and vj.
An example of a graph follows with vertices V = {v1, v2, v3, v4, v5, v6} and edges E = {e12, e13, e15, e23, e24, e26, e34, e35, e45}:
Figure 8.1 – A graph with six vertices, and nine edges connecting them
We can see, for example, the edge connecting vertex 3 (v3) to vertex 4 (v4...