21.The Basics1.1 GraphsA graph is a pair G -(V,E) of sets such that E C[V]’; thus, the elementsgraphof 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.AFig. 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 itsvertex or edge set. For example, we may speak of a vertex ue G (ratherthan u e V(G), an edge e e G, and so on.The number of vertices of a graph G is its order, written as JGl; itsordernumber of edges is denoted by Gl.Graphs are finite, infinite, countable[G], IGand so on according to their order. Except in Chapter 8, our graphs willbe finite unless otherwise stated.erivialFor the empty graph (0, 0)we simply write 0. Agraph of order 0 or1is called trivial. Sometimes, e.g. to start an induction, trivial graphs cangraphbe useful; at other times they form silly counterexamples and become anuisance. To avoid cluttering the text with non-triviality conditions, weshall mostly treat the trivial graphs, and particularly the empty graph Owith generous disregard.incidentA vertex v is incident with an edge e if v e e; then e is an edge at y.The two vertices incident with an edge are its endvertices or ends, andendsan edge joins its ends. An edge (r,y) is usually written as ry (or yr).If 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 is denoted by E(u)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)