1
A First Encounter with Graphs

1.1. A few definitions

There is not much fun in listing basic definitions about graphs (this is quite a bad introduction to start with!) but if we seek a rigorous presentation of results and proofs, then we cannot avoid giving accurate definitions of the objects that we will manipulate, but hopefully nice examples will also come quickly. In this book, we assume that the reader has a basic (or, at least a naive) knowledge of sets and operations on them.

As usual in mathematics, a pair (u, v) made up of two elements is implicitly assumed to be ordered: it has a first component u and a second component v. It has to be compared with a set with two elements u and v denoted by {u, v}. A set does not carry any ordering information about its elements. In particular, if u ? v, then we can build two pairs but a single set: (u, v) ? (v, u) and {u, v} = {v, u}. If S is a finite set, we will write #S to denote the number of elements in S, i.e. the cardinality of S. We can also find the notation |S| but we will use it to denote lengths of paths.

1.1.1. Directed graphs

DEFINITION 1.1.- Let V be an arbitrary set. A directed graph, or digraph, is a pair G = (V, E) where E is a subset of the Cartesian product V × V, i.e. E is a set of pairs of elements in V. The elements of V are the vertices of G - some authors also use the term nodes - and the elements of E are the edges, also called oriented edges or arcs1, of G. An edge of the form (v, v) is a loop on v. Another way to express that E is a subset of V × V is to say that E is a binary relation over V. If either (u, v) or (v, u) belongs to E, the vertices u and v are adjacent. If neither (u, v) nor (v, u) belong to E, then u and v are independent. Given a digraph G, the set of vertices (respectively of edges) of G is denoted by V(G) (respectively E(G)).

The vast majority of the graphs that we will encounter are finite meaning that the set V of vertices is finite, and thus E contains at most (#V)2 edges.

REMARK 1.2.- It is common to speak of the order of G for #(V(G)) and the size of G for #(E(G)).

There are a few examples of infinite graphs in this book; see examples 1.47 and 4.11 (in formal language theory) and section 7.2 about colorings. Infinite graphs usually require more sophisticated arguments such as the axiom of choice. Implementation of infinite graphs in a computer could be tricky or impossible. From a practical point of view, particular instances of infinite graphs with a countable number of vertices and edges can be implemented. Think about a periodic graph that permits one to store only a finite amount of information to be repeated or a relation among vertices that can be computed and implemented as a function (see exercise 6 and example 1.5).

A digraph G = (V, E) is said to be simple if E is a subset of (V × V) \ {(v, v) | v ? V}. In that case, the relation E is irreflexive. Otherwise stated, loops are not allowed.

The elements belonging to a set are pairwise distinct: there is no repeated element. What we need to define a directed multigraph, i.e. a digraph where multiple edges between two vertices are allowed, is to permit repetitions of an element belonging to a set. In set theory, we can introduce the notion of a multiset. First, we restrict ourselves to multisets with finite integer multiplicities. A multiset M is a pair (S, m) where S is a set, in the "classical" sense, and m : S N=1 is a multiplicity function that specifies the number m(s) of occurrences of s ? S in the multiset. As an example, the multiset denoted by {u, u, v, v, v, w} is built from S = {u, v, w} and m(u) = 2, m(v) = 3, m(w) = 1. If the occurrences of an element have to be distinguished2, we can index elements s ? S by s1,., sm(s). To continue the example, {u1, u2, v1, v2, v3, w1} denotes the same multiset as above. If S is a finite set, then the cardinality of the multiset M = (S, m) with finite multiplicities is

Observe that a multiset (S, m) where m(s) = 1, for all s ? S, is simply a set. Equivalently, we could have defined the multiplicity function to map every element s of S to a finite subset of N: the set of indices used for s.

Second, we could consider countable multiplicities3. In that case, an element of a multiset can be repeated infinitely many times and the multiplicity function maps every element to a subset of N (which is the set of indices used for that element). As an example, a vertex u could be repeated infinitely many times with prime indices: {u2, u3, u5, u7, u11, .}. Thus, the multiplicity function maps u to the set of prime numbers.

We now introduce a directed multigraph as a pair G = (V, E) where V is a set of vertices and E is a multiset of edges built from a subset of V × V. For a directed multigraph G = (V, E), the fact that V is finite does not imply that E is also finite. Indeed, we could have infinitely many edges between two vertices. Thus, a directed multigraph is finite if both the set V and the multiset E are finite.

REMARK 1.3.- It is common (and quite visual) to represent the vertices of a digraph by points in the plane (but we can also draw graphs on other surfaces like on a torus). Edges of the form (u, v) are represented by arrows going from u to v. We say that u (resp. v) is the origin (respectively, destination) of the edge. Actually any oriented arc of a curve can be used to join two vertices, not only straight vectors. Since positions of the vertices and arcs of curves joining the vertices can be freely chosen, there are usually infinitely many ways to represent a given graph. There is no reason that two edges that are intersecting in one representation are also intersecting in another representation of the same graph. We will rediscuss these notions with great care in section 6.1.

In Figure 1.1, we have depicted representations of a simple digraph, digraph and directed multigraph.

Figure 1.1. From left to right: a simple digraph, a digraph and a directed multigraph

A digraph G can be stored as an adjacency list: with each vertex u is associated the list of vertices v such that (u, v) ? E(G). For the central digraph in Figure 1.1, the corresponding adjacency list is given in Table 1.1. A similar data structure can be used for directed multigraphs.

Table 1.1. An adjacency list

EXAMPLE 1.4 (Tournament).- A simple digraph G = (V, E) where, for all pairs of distinct vertices u and v, either (u, v) or (v, u) belongs to E (but exactly one of these two edges belongs to E) is said to be a tournament. Indeed, it corresponds to an all-play-all tournament: each player plays against every other player and there are no ties. If u wins the confrontation against v, then we take the edge (v, u). See Figure 1.2.

EXAMPLE 1.5.- For an example of infinite simple digraph, take N>1 as set of vertices and a pair (m, n) of integers greater than 1 is an edge if and only if m divides n. The first few vertices and some edges of this digraph are depicted in Figure 1.3. Note that the relation E is transitive. If (m, n) and (n, p) belong to E, then (m, p) belongs to E.

Figure 1.2. A tournament among four players or teams

Figure 1.3. A divisibility relation (first few vertices only)

EXAMPLE 1.6.- We consider the digraph made up of Webpages and there is an edge from a page p to a page q if there is a link on p referencing q. This digraph is finite but contains several billions of vertices. Independently of the content of the pages, here we are interested in the links that one user can follow by browsing through pages. Based on Perron's theorem (theorem 9.2), we will discuss the basis of the Google's PageRank algorithm in Chapter 10.

Figure 1.4. Some links and...