Advanced Graph Theory and Combinatorics

1A 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 arcs¹, of G. An edge of the form (v, v) is a loop on v. Another ...