121 Graphs1.1.23 Let G be a simple graph.a) Show that G has adjacency matrix J-I-A.b)Suwthat Gisk-regui)Deduce from Exercise 1.1.22 thatalueofG.with-is.arcorresponding eigenvector 1.nvalue of G different from k, then -1 - X isii)Showthat ifisanan eigenvalue of G, with the same multiplicity. (Recall that eigenvectorscorresponding to distinct eigenvalues of a real symmetric matrix are or-thogonal.)1.1.24 Show that:a) no eigenvalue of a graph G has absolute value greater than △,b) if G is a connected graph and △ is an eigenvalue of G, then G is regular.) if G is a connected graph and - is an eigenvalue of G, then G is both regulalndbipartite1.1.25 STRONGLYREGULAR GRAPHA simple graph G which is neither empty nor complete is said to be strongly regularwith parameters (u,k, ,p) if:v(G) = 1Gis k-regularDany two adjacent vertices of G have A common neighboursany two nonadjacent vertices of G have μ common neighbours.Let G bea strongly regular graph with parameters (u,k, >,μ). Show that:a) G is strongly regularb) k(k- ^- 1) = (u - k - 1)μ,C) A-hI+AA+μ(J-I-A).1.2 Isomorphisms and AutomorphismsISOMORPHISMSTwo graphs G and H are identical, written G = H, if V(G) = V(H), E(G) ()ndwographadentical,thyanclearlyentedbyidentical diagHowever, it is also possible for graphs that are not identical tohave essentilly thesame diagram.For example, the graphs G and H in Figure 6e represented by diagrams which look exactly the same, as the second drawingof H shows; the sole difference lies in the labels of their vertices and edges. Althoughthe graphs G and H are not identical, they do have identical structures, and aresaid tobeisomorphiIn general, two graphs G and H are isomorphic, written G = H, if there arebijections :V(G)V(H)and @:E(G)-E(H)such that c(e)=uvif andonly if h(s(e) = e(u)e(u); such a pair of mappings is called an isomorphismbetween G and H.12 1 Graphs 1.1.23 Let G be a simple graph. a) Show that G has adjacency matrix J − I − A. b) Suppose now that G is k-regular. i) Deduce from Exercise 1.1.22 that n − k − 1 is an eigenvalue of G, with corresponding eigenvector 1. ii) Show that if λ is an eigenvalue of G different from k, then −1 − λ is an eigenvalue of G, with the same multiplicity. (Recall that eigenvectors corresponding to distinct eigenvalues of a real symmetric matrix are or￾thogonal.) 1.1.24 Show that: a) no eigenvalue of a graph G has absolute value greater than ∆, b) if G is a connected graph and ∆ is an eigenvalue of G, then G is regular, c) if G is a connected graph and −∆ is an eigenvalue of G, then G is both regular and bipartite. 1.1.25 Strongly Regular Graph A simple graph G which is neither empty nor complete is said to be strongly regular with parameters (v,k,λ,µ) if:  v(G) = v,  G is k-regular,  any two adjacent vertices of G have λ common neighbours,  any two nonadjacent vertices of G have µ common neighbours. Let G be a strongly regular graph with parameters (v,k,λ,µ). Show that: a) G is strongly regular, b) k(k − λ − 1) = (v − k − 1)µ, c) A2 = k I + λ A + µ (J − I − A). 1.2 Isomorphisms and Automorphisms Isomorphisms Two graphs G and H are identical, written G = H, if V (G) = V (H), E(G) = E(H), and ψG = ψH. If two graphs are identical, they can clearly be represented by identical diagrams. However, it is also possible for graphs that are not identical to have essentially the same diagram. For example, the graphs G and H in Figure 1.6 can be represented by diagrams which look exactly the same, as the second drawing of H shows; the sole difference lies in the labels of their vertices and edges. Although the graphs G and H are not identical, they do have identical structures, and are said to be isomorphic. In general, two graphs G and H are isomorphic, written G ∼= H, if there are bijections θ : V (G) → V (H) and φ : E(G) → E(H) such that ψG(e) = uv if and only if ψH(φ(e)) = θ(u)θ(v); such a pair of mappings is called an isomorphism between G and H