141 Graphs（123456)OacedfbIsomorphic graphs clearly have the same numbers of vertices and edges. Onthe other hand, equality of these parameters does not guarantee isomorphism. Forinstance, the two graphs shown in Figure 1.8 both have eight vertices and twelveedges, but they are not isomorphic. To see this, observe that the graph G has fourmutually nonadjacent vertices, v1, 23, V6, and vs. If there were an isomorphism ebetween G and H, the vertices (ui), e(v3), (v6), and e(us) of H would likewisbemutually nonadjacent.Butit canreadily bechecked that nofourvertices ofHare mutually nonadjacent. We deduce that G and H are not isomorphic.TFig. 1.8. NonisoomorphicgraphsIt is clear from the foregoing discussion that if two graphs are isomorphic, thenthey are either identical or differ merely in the names of their vertices and edgesand thus have the same structure. Because it is primarily in structural propertiesthat we are interested, we often omit labels when drawing graphs; formally, we maydefine an unlabelled graph as a representative ofan equivalence class of isomorphicgraphs. We assign labels to vertices and edges in a graph mainly for the purposeof refering to them (in proofs, for instance).Up to isomorphism, there is just one complete graph on n vertices, denoted KnSimilarly, given two positive integers m and n, there is a unique complete bipartitegraph with parts of sizes m and n (again, up to isomorphism), denoted Km.nIn this notation, the graphs in Figure 1.2 are Ks, K3.3, and Ki,5, respectively.Likewise, for any positive integer n, there is a unique path on n vertices and aunique cycle on n vertices.These graphs are denoted Pn and Cn,respectively.Thegraphs depicted in Figure 1.3 are Pr and Cs.TESTING FOR ISOMORPHISMGiven two graphs on n vertices, it is certainly possible in principle to determinwhethertheyFor instance, if G and H arple,onecouldjustconsider each of the n! bijections between V(G) and V(H) in turn, and check14 1 Graphs θ :=  123456 acedfb  Isomorphic graphs clearly have the same numbers of vertices and edges. On the other hand, equality of these parameters does not guarantee isomorphism. For instance, the two graphs shown in Figure 1.8 both have eight vertices and twelve edges, but they are not isomorphic. To see this, observe that the graph G has four mutually nonadjacent vertices, v1, v3, v6, and v8. If there were an isomorphism θ between G and H, the vertices θ(v1), θ(v3), θ(v6), and θ(v8) of H would likewise be mutually nonadjacent. But it can readily be checked that no four vertices of H are mutually nonadjacent. We deduce that G and H are not isomorphic. v1 v2 v1 v2 v3 v3 v4 v4 v5 v6 v5 v6 v7 v7 v8 v8 G H Fig. 1.8. Nonisomorphic graphs It is clear from the foregoing discussion that if two graphs are isomorphic, then they are either identical or differ merely in the names of their vertices and edges, and thus have the same structure. Because it is primarily in structural properties that we are interested, we often omit labels when drawing graphs; formally, we may define an unlabelled graph as a representative of an equivalence class of isomorphic graphs. We assign labels to vertices and edges in a graph mainly for the purpose of referring to them (in proofs, for instance). Up to isomorphism, there is just one complete graph on n vertices, denoted Kn. Similarly, given two positive integers m and n, there is a unique complete bipartite graph with parts of sizes m and n (again, up to isomorphism), denoted Km,n. In this notation, the graphs in Figure 1.2 are K5, K3,3, and K1,5, respectively. Likewise, for any positive integer n, there is a unique path on n vertices and a unique cycle on n vertices. These graphs are denoted Pn and Cn, respectively. The graphs depicted in Figure 1.3 are P4 and C5. Testing for Isomorphism Given two graphs on n vertices, it is certainly possible in principle to determine whether they are isomorphic. For instance, if G and H are simple, one could just consider each of the n! bijections between V (G) and V (H) in turn, and check