1.4 Constructing Graphs from Other Graphs291.4 Constructing Graphs from Other GraphsWe have already seen a couple of ways in which we may associate with each graphanother graph: the complement (in the case of simple graphs) and the line graph.If we start with two graphs G and H rather than just one, a new graph may bedefined in several ways. For notational simplicity, we assume that G and H aresimple, so that each edge is an unordered pair of vertices; the concepts describedherecanbeextended without difficulty tothegeneral contextUNION AND INTERSECTIONTwo graphs are disjoint if theyhave no vertex in common, and edge-disjointifthey have no edge in common. The most basic ways of combining graphs are byThe union of simple graphs G and H is the graph GUHunionand intersectiolwith vertex set V(G)UV(H) and edge set E(G)UE(H). If G and H are disjoint.we refer to their union as a disjoint union, and generally denote it by G+HThese operations are associative and comnutative, and may be extended to anarbitrary number of graphs. It can be seen that a graph is disconnected if andonly if itisa disjointnion of two (nonnull) graphs. More generally, every graphG may be expressed uniquely (up to order) as a disjoint union of connected graphs(Exercise 1.4.1). These graphs are called the connected components, or simply thecomponents, of G.The number of components of G is denoted c(G). (The nullgraph has the anomalous property of being the only graph without components.)The intersection GnH of Gand H is defined analogously.(NotethatwherG and H are disjoint, their intersection is the null graph.) Figure 1.22 illustratesheseconcepts.ThegraphGUHshown inFigure1.22has just onecomponentwhereas the graph Gn H has two components.03GHGUHGnHFig. 1.22. The union and intersection of two graphsCARTESIANPRODUCTThere are also several ways offorming from two graphs a new graph whose verteset is the cartesian product of their vertex sets.These constructions are consequently referred to as 'products'. We now describe one of them.1.4 Constructing Graphs from Other Graphs 29 1.4 Constructing Graphs from Other Graphs We have already seen a couple of ways in which we may associate with each graph another graph: the complement (in the case of simple graphs) and the line graph. If we start with two graphs G and H rather than just one, a new graph may be defined in several ways. For notational simplicity, we assume that G and H are simple, so that each edge is an unordered pair of vertices; the concepts described here can be extended without difficulty to the general context. Union and Intersection Two graphs are disjoint if they have no vertex in common, and edge-disjoint if they have no edge in common. The most basic ways of combining graphs are by union and intersection. The union of simple graphs G and H is the graph G ∪ H with vertex set V (G) ∪ V (H) and edge set E(G) ∪ E(H). If G and H are disjoint, we refer to their union as a disjoint union, and generally denote it by G + H. These operations are associative and commutative, and may be extended to an arbitrary number of graphs. It can be seen that a graph is disconnected if and only if it is a disjoint union of two (nonnull) graphs. More generally, every graph G may be expressed uniquely (up to order) as a disjoint union of connected graphs (Exercise 1.4.1). These graphs are called the connected components, or simply the components, of G. The number of components of G is denoted c(G). (The null graph has the anomalous property of being the only graph without components.) The intersection G ∩ H of G and H is defined analogously. (Note that when G and H are disjoint, their intersection is the null graph.) Figure 1.22 illustrates these concepts. The graph G ∪ H shown in Figure 1.22 has just one component, whereas the graph G ∩ H has two components. 11 1 2 2 2 1 2 4 5 3 4 3 5 3 3 GH G ∪ H G ∩ H Fig. 1.22. The union and intersection of two graphs Cartesian Product There are also several ways of forming from two graphs a new graph whose vertex set is the cartesian product of their vertex sets. These constructions are conse￾quently referred to as ‘products’. We now describe one of them