1.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 and 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 v5 are incident.

If it does not make inconvenience then we will use the notation v1,v2 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.