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.