21. The Basics1.1 GraphsA graph is a pair G=(V,E) of sets such that E C [V]?; thus, theelementsgraphof E are 2-element subsets of V. To avoid notational ambiguities, weshall always assume tacitly that VnE = 0. The elements of V are thevertices (or nodes, or points) of the graph G, the elements of E are itsvertexedgeedges (or lines). The usual way to picture a graph is by drawing a dot foreach vertex and joining two of these dots by a line if the correspondingtwo vertices form an edge. Just how these dots and lines are drawn isconsidered irrelevant: all that matters is the information of which pairsof vertices form an edge and which do not.Fig. 1.1.1. The graph on V = [1,--, 7) with edge setE = [(1,2], [1,5], [2,5], [3,4], [5, 7)]A graph with vertex set V is said to be a graph on V. The vertexonV(G),E(G) set of a graph G is referred to as V(G), its edge set as E(G). Theseconventions are independent of any actual names of these two sets: thevertex set W of a graph H = (W, F) is still referred to as V(H), not asW(H). We shall not always distinguish strictly between a graph and itsDr edge set. For example, we may speak of a vertex ue G (ratherortXthan u e V(G)), an edge e e G, and so olorderThe number of vertices of a graph G is its order, written as [Gl; itsJG, JIGInumber of edges is denoted by Gll. Graphs are finite, infinite, countableand so on according to their order. Except in Chapter 8, our graphs willbe finite unless otherwisestatedFor the empty graph (0, 0) we simply write 0. A graph of order 0 or 1trivialis called trivial. Someg.to start an induction,trivialgraphscantimegraphbe useful; at other times they form silly counterexamples and become aquisance.To avoid cluttering the text with non-triviality conditions.weshall mostly treat the trivial graphs, and particularly the empty graphwith generous disregardincident.A vertex v is incident with an edge e if u e e; then e is an edge at wendsThe two vertices incident with an edge are its enduertices or ends, andan edge joins its ends. An edge [z,y) is usually written as ry (or yr).If r e X and y e Y, then ry is an X-Y edge. The set of all X-Y edgesE(X,Y)in a set E is denoted by E(X,Y); instead of E((r),Y) and E(X, (y))we simply write E(r,Y) and E(X,y). The set of all the edges in E at aE(u)vertex u is denoted by E(v).2 1. The Basics 1.1 Graphs A graph is a pair G = (V,E) of sets such that E ⊆ [V ] 2 graph ; thus, the elements of E are 2-element subsets of V . To avoid notational ambiguities, we shall always assume tacitly that V ∩ E = ∅. The elements of V are the vertex vertices (or nodes, or points) of the graph G, the elements of E are its edge 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. 1 2 3 4 5 6 7 Fig. 1.1.1. The graph on V = {1,..., 7} with edge set E = {{1, 2}, {1, 5}, {2, 5}, {3, 4}, {5, 7}} on A graph with vertex set V is said to be a graph on V . The vertex V (G), E(G) 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 ∈ G (rather than v ∈ V (G)), an edge e ∈ G, and so on. order The number of vertices of a graph G is its order, written as |G|; its |G|, G number of edges is denoted by 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 (∅, ∅) we simply write ∅. A graph of order 0 or 1 is called trivial. Sometimes, e.g. to start an induction, trivial graphs can trivial graph 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 ∅, with generous disregard. incident A vertex v is incident with an edge e if v ∈ e; then e is an edge at v. ends The two vertices incident with an edge are its endvertices or ends, and an edge joins its ends. An edge {x, y} is usually written as xy (or yx). If x ∈ X and y ∈ Y , then xy is an X–Y edge. The set of all X–Y edges E(X, Y ) in a set E is denoted by E(X, Y ); instead of E({x}, Y ) and E(X, {y}) we simply write E(x, Y ) and E(X, y). The set of all the edges in E at a E(v) vertex v is denoted by E(v)