This Chapter gives an introduction to most of the terminology used later in the book.

By \(\N\) we denote the set of natural numbers, including zero. The set \(\Z/n\Z\) of integers modulo \(n\) is denoted by \(\Z_n\); its elements are written as \(\bar i := i + n\Z\). When we regard \(\Z_2 = \set{\bar 0, \bar 1}\) as a field, we also denote it as \(\F_2 = \set{0, 1}\). For a real number \(x\) we denote by \(\floor{x}\) the greatest integer \(\le x\), and by \(\ceil{x}\) the least integer \(\ge x\). Logarithms written as ‘log’ are taken at base \(2\); the natural logarithm will be denoted by ‘ln’. The expression \(x := y\) and \(y =: x\) mean that \(x\) is being defined as \(y\).

A set \(\mathcal{A} = \set{A_1, \dots, A_k}\) of disjoint subsets of a set \(A\) is a partition of \(A\) if the union \(\bigcup \mathcal{A}\) of all the sets \(A_i\in \mathcal{A}\) is \(A\) and \(A_i \ne \emptyset\) for every \(i\). Another partition \(\set{A_1', \dots, A_\ell'}\) of \(A\) refines the partition \(\mathcal{A}\) if each \(A'_i\) is contained in some \(A_j\). By \([A]^k\) we denote the set of all \(k\)-element subsets of \(A\). Sets with \(k\) elements will be called \(k\)-sets; subsets with \(k\) elements are \(k\)-subsets.

Graphs

A graph is a pair \(G = (V, E)\) of sets such that \(E \sube [V]^2\); thus, the elements of \(E\) are 2-element subsets of \(V\). To avoid notational ambiguities, we shall always assume tacitly that \(V \cap E = \emptyset\). The elements of \(V\) are the vertices (or nodes, or points) of the graph \(G\), the elements of \(E\) are its edges (or lines). The usual way to picture a graph is by drawing a dot for each vertex and joining two of these dots by a line if the corresponding two vertices form an edge. Just how these dots and lines are drawn is considered irrelevant: all that matters is the information of which pairs of vertices form an edge and which do not.

A graph with vertex set \(V\) is said to be a graph on \(V\). The vertex set of a graph \(G\) is referred to as \(V(G)\), its edge set as \(E(G)\). These conventions are independent of any actual names of these two sets: the vertex set \(W\) of a graph \(H = (W, F)\) is still referred to as \(V(H)\), not as \(W(H)\). We shall not always distinguish strictly between a graph and its vertex or edge set. For example, we may speak of a vertex \(v\in G\) (rather than \(v\in V(G)\)), and edge \(e\in G\), and so on.

The number of vertices of a graph \(G\) is its order, written as \(|G|\); its number of edges is denoted as \(\norm{G}\). Graphs are finite, infinite, countable and so on according to their order. Except in Chapter 8, our graphs will be finite unless otherwise stated.

For the empty graph \((\emptyset, \emptyset)\) we simply write \(\emptyset\). A graph of order \(0\) or \(1\) is called trivial. Sometimes, e.g. to start an induction, trivial graphs can be useful; at other times they form silly counterexamples and become a nuisance. To avoid cluttering the text with non-triviality conditions, we shall mostly treat the trivial graphs, and particularly the empty graph \(\emptyset\), with generous disregard.

A vertex \(v\) is incident with an edge \(e\) if \(v\in e\); then \(e\) is an edge at \(v\). The two vertices incident with an edge are its endvertices or ends, and an edge joins its ends. An edge \(\set{x, y}\) is usually written as \(xy\) (or \(yx\)). If \(x\in X\) and \(y\in Y\), then \(xy\) is an \(X-Y\) edge. The set of all \(X-Y\) edges in a set \(E\) is denoted by \(E(X, Y)\); instead of \(E(\set{x}, Y)\) and \(E(Y, \set{x})\) we simply write \(E(x, Y)\) and \(E(X, y)\). The set of all the edges in \(E\) at a vertex \(v\) is denoted by \(E(v)\).

Two vertices \(x\), \(y\) of \(G\) are adjacent, or neighbours, if \(\set{x, y}\) is an edge of \(G\). Two edges \(e \ne f\) are adjacent if they have an end in common. If all the vertices of \(G\) are pairwise adjacent, then \(G\) is a complete. A complete graph on \(n\) vertices is a \(K^n\); a \(K^3\) is called a triangle.

A set of vertices or of edges is independent if no two of its elements are adjacent. Independent sets of vertices are also called stable.

Let \(G = (V, E)\) and \(G'=(V',E')\) be two graphs. A map \(\varphi: V \to V'\) is a homomorphism from \(G\) to \(G'\) if it preserves the adjacency of vertices, that is, if \(\set{\varphi(x), \varphi(y)} \in E'\) whenever \(\set{x, y} \in E\). Then, in particular, every vertex \(x'\) in the image of \(\varphi\) its inverse image \(\varphi^{-1}(x')\) is an independent set of vertices in \(G\). If \(\varphi\) is bijective and its inverse \(\varphi^{-1}\) is also a homomorphism (so that \(xy \in E \iff \varphi(x)\varphi(y) \in E'\) for all \(x, y\in V\)), we call \(\varphi\) an isomorphism, say that \(G\) and \(G'\) are isomorphic, and write \(G \iso G'\). An isomorphism form \(G\) to itself is an automorphism of \(G\).

We do not normally distinguish between isomorphic graphs. Thus, we usually write \(G = G'\) rather than \(G \iso G'\), speak of the complete graph on 17 vertices, and so on. If we wish to emphasize that we are only interested in the isomorphism type of a give graph, we informally refer to it as an abstract graph.

A class of graphs that is closed under isomorphism is called a graph property. For example, ‘containing a triangle’ is a graph property: if \(G\) contains three pairwise adjacent vertices then so does every graph isomorphic to \(G\). A map taking graphs as arguments is called a graph invariant if it assigns equal values to isomorphic graphs. The number of vertices and the number of edges of a graph are two simple graph invariants; the greatest number of pairwise adjacent vertices is another.

We set \(G \cup G' := (V \cup V', E \cup E')\) and \(G \cap G' := (V \cap V', E \cap E')\). If \(G \cup G' = \nil\), then \(G\) and \(G'\) are disjoint. If \(V' \sube V\) and \(E' \sube E\), then \(G'\) is a subgraph of \(G\) (and \(G\) a supergraph of \(G'\)), written as \(G' \sube G\). Less formally, we say that \(G\) contains \(G'\). If \(G' \sube G\) and \(G' \ne G\), then \(G'\) is a proper subgraph of \(G\).

Connectivity

A graph \(G\) is called connected if it is non-empty and any two of its vertices are linked by a path in \(G\). If \(U \sube V(G)\) and \(G[U]\) is connected, we also call \(U\) itself connected (in \(G\)). Instead of ‘not connected’ we usually say ‘disconnected’.

Some linear algebra

A set \(F\) of edges is a cut in \(G\) if there exists a partition \(\set{V_1, V_2}\) of \(V\) such that \(F = E(V_1, V2)\). The edges in \(F\) are said to cross this partition. The sets \(V_1\), \(V2\) are the sides of the cut. Recall that for \(V_1 = \set{v}\) this cut is denoted by \(E(v)\). A minimal non-empty cut in \(G\) is a bond.

Other notions of graphs

For completeness, we now mention a few other notions of graphs which feature less frequently or not at all in this book.

A hypergraph is a pair \((V, E)\) of disjoint sets, where the elements of \(E\) are non-empty subsets (of any cardinality) of \(V\). Thus, graphs are special hypergraphs.

A directed graph (or digraph) is a pair \((V, E)\) of disjoint sets (of vertices and edges) together with two maps \(\init : E \to V\) and \(\ter : E \to V\) assigning to every edge \(e\) an initial vertex \(\init(e)\) and a terminal vertex \(\ter(e)\). The edge \(e\) is said to be directed from \(\init(e)\) to \(\ter(e)\). Note that a directed graph may have several edges between the same two vertices \(x, y\). Such edges are called multiple edges; if they have the same direction (say from \(x\) to \(y\)), they are parallel. If \(\init(e) = \ter(e)\), the edge \(e\) is called a loop.

A directed graph \(D\) is an orientation of an (undirected) graph \(G\) if \(V(D) = V(G)\) and \(E(D) = E(G)\), and if \(\set{\init(e), \ter(e)} = \set{x, y}\) for every edge \(e = xy\). Intuitively, such as oriented graph arises from an undirected graph simply by directing every edge from one of its ends to the other. Put differently, oriented graphs are directed graphs without loops or multiple edges.

A multigraph is a pair \((V, E)\) of disjoint sets (of vertices and edges) together with a map \(E \to V \cup [V]^2\) assigning to every edge either one or two vertices, its ends. Thus, multigraphs too can have loops and multiple edges: we may think of a multigraph as a directed graph whose edge directions have been ‘forgotten’. To express that \(x\) and \(y\) are the ends of an edge \(e\) we still write \(e = xy\), though this no longer determines \(e\) uniquely.

A graph is thus essentially the same as a multigraph without loops or multiple edges. Somewhat surprisingly, proving a graph theorem more generally for multigraphs may, on occasion, simplify the proof. Moreover, there are areas in graph theory where multigraphs arise more naturally than graphs, and where any restriction to the latter would seem artificial and be technically complicated. We shall therefore consider multigraphs in these cases, but without much technical ado: terminology introduce earlier for graphs will be used correspondingly.

A few differences, however, should be pointed out. A multigraph may have cycles of length \(1\) or \(2\): loops, and pairs of multiple edges (or double edges). A loop at a vertex makes it its own neighbor, and contributes \(2\) to its degree.