2.1.1. Vertices and edges
A graph G is a finite nonempty set of objects - called as vertices - together with a (possibly empty) set of unordered pairs of distinct vertices of G called edges. We will denote by V(G) and E(G) the vertex set of G and the edge set of G, respectively.
The next figure illustrates the certain definitions for the elements.
Figure 2.1. Graphical representation of a graph
We will say that
- edge e1 = {v1,v4} joins the vertices v1 and v4;
- v3 and v2 are adjacent vertices;
- e3 and e4 are adjacent edges; and
- e4 and e5 are incident.
If it does not make inconvenience then we will use the notation v1v2 instead of {v1,v2}.
The cardinality of the vertex set of a graph G is the order of G, the cardinality of the edge set of a graph G is the size of G and they are denoted by n(G) and m(G), respectively. A graph G with order n and size m is denoted by G(n,m) or Gn,m. A graph with no edges is called an empty graph.