1.1 Graphses r, y ofG are adjacent, or neighbours, if (r,y) is an edgeadjacentof G. Two edges e + f are adjacent if they have an end in common. If allneighbourthe vertices of G are pairwise adjacent, then G is complete. A completecompleteKngraph on n vertices is a Kn; a K3 is called a triangle. are called independent.Pairwise non-adiacent vertices or edgespelaneMore formally, a seor of edges is indenendent if notwoof itstoforticoselenadjacent.IndependentsetsofverticesarealsocalledstableLet G= (V,E) and G'- (V', E') be two graphs. A map p:V-V"mophnisahommorphism from G to G' ifit preserves the adjacency of vertices,that is, if (o(r), p(y)) E' whenever (r,y) e E. Then, in particularfor every vertex r' in the image of its inverse image p-'(r') is anindependent set of vertices in G.If ois biiective and its inverse11also a homomorphism (so that ry e E p(r)p(y) e E' for all , y e V),rphism,saythatG and G'are isomorphic.writeisomorphicG - G'. An isomorphism from G to itself is an automorphism of G.2We do not normally distinguish between isomorphic graphs.Thus,we usually write G = G' rather than G ~ G', speak of the completegraph on 17 vertices, and so on. If we wish to emphasize that we areonly interested in the isomorphism type of a given graph, we informallyrefer to it aanabstractgraphA class of graphs that is closed under isoorphiscalled a graphproperty.For example, containing a triangle'is a graph property: ifpropertyG contains three pairwise adjacent vertices then so does every graphisomorphic to G. A map taking graphs as arguments is called a graphinvariant if it assigns equal values to isomorphic graphs. The numberinvariantof vertices and the number of edges of a graph are two simple graphinvariants: the greatest number of pairwise adiacent vertices is anotherWe set GUG' := (VUV',EUE') and GnG' := (VnV', EnE').GUQIf GnG'=0,then G and G' are disjont.IfVCVand E'E,thenGnG'2GL1..42GnG'GUGG-GFig.2. Union,diference and intersection the vertices23induce (or span) a triangle in GUG' but not in G1.1 Graphs 3 Two vertices x, y of G are adjacent, or neighbours, if {x, y} is an edge adjacent of G. Two edges e = f are adjacent if they have an end in common. If all neighbour the vertices of G are pairwise adjacent, then G is complete. A complete complete graph on n vertices is a Kn; a K3 is called a triangle. Kn Pairwise non-adjacent vertices or edges are called independent. More formally, a set of vertices or of edges is independent if no two of its inde￾pendent elements are adjacent. Independent sets of vertices are also called stable. Let G = (V,E) and G = (V , E ) be two graphs. A map ϕ: V →V is a homomorphism from G to G if it preserves the adjacency of vertices, homo￾morphism that is, if {ϕ(x), ϕ(y)} ∈ E whenever {x, y} ∈ E. Then, in particular, for every vertex x in the image of ϕ its inverse image ϕ−1(x ) is an independent set of vertices in G. If ϕ is bijective and its inverse ϕ−1 is also a homomorphism (so that xy ∈ E ⇔ ϕ(x)ϕ(y) ∈ E for all x, y ∈ V ), we call ϕ an isomorphism, say that G and G are isomorphic, and write isomorphic G  G . An isomorphism from 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  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 given 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 property 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 invariant 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 ∪ G := (V ∪ V , E ∪ E ) and G ∩ G := (V ∩V , E ∩ E ). G ∪ G If G ∩ G = ∅, then G and G are disjoint. If V ⊆ V and E ⊆ E, then G ∩ G G ∪ − G G ∩ 1 2 3 4 5 G 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 G G G G Fig. 1.1.2. Union, difference and intersection; the vertices 2,3,4 induce (or span) a triangle in G ∪ G but not in G