21 GraphsFor example, the points could represent people, with lines joining pairs of friends; orcation centres.with lines repiepointsmightbecolcatiorglinks. Notice that in such diagrams one is mainly interested in whether two givenpoints are joined by a line; the manner in which they are joined is immaterial. Amathematical abstraction of situations of this type gives rise to the concept of agraph.A graph G is an ordered pair (V(G),E(G) consisting of a set V(G) of verticesand a set E(G), disjoint from V(G),of edges, together with an incidence functionWc that asciates with each edge of G anunordered pair of (not.necessarilydistinct) vertices of G. If e is an edge and u and are vertices such that bc(e) -[u.ul.the is said to joinuand w,and the vertices u and y are called the endsof e. We denote the numbers of vertices and edges in G by v(G) and e(G); thesetwobasicparametersarecalledtheorderand szeofGrespectivelyTwo examples of graphs should serve to clarify the definition. For notationalsimplicity, we write uu for the unordered pair [u,].Erample 1.G = (V(G),E(G)whereV(G)= fu,u,w,r,y)E(G) = (a,b,c,d,e, f,g,h)and wc is defined byve(a) = c(b) =uu c(c) =ww we(d)= wadc(e) = va c(f) = wr wc(g) =ur c(h) = ryErample 2.H =(V(H),E(H)whereV(H) = [o, 1, 2, U3, 4,05]E(H)- (e1e2,e,e,e,e,,es,e,and wh is defined bybh(ei)=uiu2 bh(e2) = u2us wr(es) =vau wh(es) = vaus bh(es)= Usuih(e6)= ouh(e7)=ou2 h(es)=Voua (eo)=Vou h(e10)=PovsDRAWINGS OF GRAPHSGraphs are so named because they can be represented graphically, and it is thisgraphical representation which helps us understand many of their properties. Eachvertex is indicated by a point, and each edge by a line joining the points representing its ends. Diagrams of G and H are shown in Figure 1.1. (For clarity, verticesare represented by small circles.)2 1 Graphs For example, the points could represent people, with lines joining pairs of friends; or the points might be communication centres, with lines representing communication links. Notice that in such diagrams one is mainly interested in whether two given points are joined by a line; the manner in which they are joined is immaterial. A mathematical abstraction of situations of this type gives rise to the concept of a graph. A graph G is an ordered pair (V (G),E(G)) consisting of a set V (G) of vertices and a set E(G), disjoint from V (G), of edges, together with an incidence function ψG that associates with each edge of G an unordered pair of (not necessarily distinct) vertices of G. If e is an edge and u and v are vertices such that ψG(e) = {u,v}, then e is said to join u and v, and the vertices u and v are called the ends of e. We denote the numbers of vertices and edges in G by v(G) and e(G); these two basic parameters are called the order and size of G, respectively. Two examples of graphs should serve to clarify the definition. For notational simplicity, we write uv for the unordered pair {u,v}. Example 1. G = (V (G),E(G)) where V (G) = {u,v,w,x,y} E(G) = {a,b,c,d,e,f,g,h} and ψG is defined by ψG(a) = uv ψG(b) = uu ψG(c) = vw ψG(d) = wx ψG(e) = vx ψG(f) = wx ψG(g) = ux ψG(h) = xy Example 2. H = (V (H),E(H)) where V (H) = {v0,v1,v2,v3,v4,v5} E(H) = {e1,e2,e3,e4,e5,e6,e7,e8,e9,e10} and ψH is defined by ψH(e1) = v1v2 ψH(e2) = v2v3 ψH(e3) = v3v4 ψH(e4) = v4v5 ψH(e5) = v5v1 ψH(e6) = v0v1 ψH(e7) = v0v2 ψH(e8) = v0v3 ψH(e9) = v0v4 ψH(e10) = v0v5 Drawings of Graphs Graphs are so named because they can be represented graphically, and it is this graphical representation which helps us understand many of their properties. Each vertex is indicated by a point, and each edge by a line joining the points represent￾ing its ends. Diagrams of G and H are shown in Figure 1.1. (For clarity, vertices are represented by small circles.)