91.1 Graphs and Their RepresentationExercises1.1.1 Let G be a simple graph. Show that m ≤ (2), and determine when equalityholds.1.1.2 Let G[X,Y] be a simple bipartite graph, where [X| = r and [Y| = s.a) Show that m ≤rs.b) Deduce that m<≤n2/4c) Describe the simple bipartite graphs G for which equality holds in (b)+1.1.3 Show that:a)every path is bipartite,b) a cycle is bipartite if and only if its length is even1.1.4 Show that, for any graph G, o(G) ≤ d(G)≤ 4(G).1.1.5 For k = 0, 1, 2, characterize the k-regular graphs1.1.6a) Show that, in any group of two or more people, there are always two who haveactlythesamemberoffriendswithinthegroupb)Describeagroupoffive people,anytwoof whomhaveexactlyonefriendincommon. Can you find a group of four people with this same property?1.1.7 n-CUBEThe n-cube Qn (n ≥ 1) is the graph whose vertex set is the set of all n-tuples of Osands, wheretwon-tuples areadjacent ifthey difer in precisely one coordinate.a) Draw Qi, Q2, Q3, and Q4b)Deternnine v(Qn) and e(Qn)) Show that Qn is bipartite for all n ≥11.1.8 The boolean lattice BLn (n ≥ 1) is the graph whose vertex set is theof all subsets of [1, 2,...,n), where tw7o subsets X and Y are adjacent if theirsymmetric difference hasprecisely one element.a)Draw BLi,BL2,BLs,and BLb) Determine u(BLn) and e(BLn)c) Show that BLn is bipartite for all n ≥1.+1.1.9 Let G[X, Y] be a bipartite graph.a) Show that x d(o) = Ever d(o).b) Deduce that if G is k-regular, with k ≥ 1, then [X = [Y]
1.1 Graphs and Their Representation 9 Exercises 1.1.1 Let G be a simple graph. Show that m ≤ n 2 , and determine when equality holds. 1.1.2 Let G[X,Y ] be a simple bipartite graph, where |X| = r and |Y | = s. a) Show that m ≤ rs. b) Deduce that m ≤ n2/4. c) Describe the simple bipartite graphs G for which equality holds in (b). 1.1.3 Show that: a) every path is bipartite, b) a cycle is bipartite if and only if its length is even. 1.1.4 Show that, for any graph G, δ(G) ≤ d(G) ≤ ∆(G). 1.1.5 For k = 0, 1, 2, characterize the k-regular graphs. 1.1.6 a) Show that, in any group of two or more people, there are always two who have exactly the same number of friends within the group. b) Describe a group of five people, any two of whom have exactly one friend in common. Can you find a group of four people with this same property? 1.1.7 n-Cube The n-cube Qn (n ≥ 1) is the graph whose vertex set is the set of all n-tuples of 0s and 1s, where two n-tuples are adjacent if they differ in precisely one coordinate. a) Draw Q1, Q2, Q3, and Q4. b) Determine v(Qn) and e(Qn). c) Show that Qn is bipartite for all n ≥ 1. 1.1.8 The boolean lattice BLn (n ≥ 1) is the graph whose vertex set is the set of all subsets of {1, 2,...,n}, where two subsets X and Y are adjacent if their symmetric difference has precisely one element. a) Draw BL1, BL2, BL3, and BL4. b) Determine v(BLn) and e(BLn). c) Show that BLn is bipartite for all n ≥ 1. 1.1.9 Let G[X,Y ] be a bipartite graph. a) Show that v∈X d(v) = v∈Y d(v). b) Deduce that if G is k-regular, with k ≥ 1, then |X| = |Y |
101 Graphs+1.1.10 k-PARTITE GRAPHA k-partite graph is one whose vertexcan bepartitioned into ksubsway that no edge has both ends in the same part. (Equivalentlyparts,in suchone may think of the vertices as being colourable by k colours so that no edge joinstwo vertices of the same colour.) Let G be a simple k-partite graph with parts ofsizes ai,a2...,aw. Show that m ≤IEt-- ai(n -a).+1.1.11 TURAN GRAPHA k-partite graph is complete if any two vertices in different parts are adjacent. Asimplecompletek-partitegraphon nverticeswhosepartsareof equal oralmostequal sizes (that is, [n/k] or[n/k]) is called a Turan graph and denoted Tkn.a) Show that Tkn has more edges than any other simple complete k-partite graphnvertib) Determine e(Tk.n)1.1.12a) Show that if G is simple and m > (n-1), then G is connectedb) For n>1, find a disconnected simplegraph G with m = ("=)1.1.13a) Show that if G is simple and >(n -2), then Gis connectedb) For n even, find a disconnected (n - 2)-regular simple graph.a simple graph G,show that the diagonal entries of both A?and MM1.1.14For(where M' denotes the transpose of M) are the degrees of the vertices of G.1.1.15 Show that the rank over GF(2) of the incidencece matrix of a graph G is atmost n -- 1, with equality if and only if G is connected.1.1.16 DEGREE SEQUENCE,Un, the sequence (d(ui),d(u2)..,d(on) is caled aIf G has verticesnceofG.Letd (dd..d.)beanoninereasingsequenceodegree sequenonnegative integers, that is, di ≥ d2 ≥... ≥ d, ≥0. Show that:a) there is a graph with degreesequenced if and onlyifd,isevenb) there is a loopless graph with degree sequence d if and only if r-i d, is evenanddii2d1.1.17 COMPLEMENT OF A GRAPHLet G be a simple graph. The complement G of G is the simple gra1 whose vertexset is V and whose edges are the pairs of nonadjacent vertices of Ga) Express the degree sequence ofGin terms of the degree sequence ofG.b) Show that if G is disconnected, then G is connected. Is the converse true?
10 1 Graphs 1.1.10 k-Partite Graph A k-partite graph is one whose vertex set can be partitioned into k subsets, or parts, in such a way that no edge has both ends in the same part. (Equivalently, one may think of the vertices as being colourable by k colours so that no edge joins two vertices of the same colour.) Let G be a simple k-partite graph with parts of sizes a1,a2,...,ak. Show that m ≤ 1 2 k i=1 ai(n − ai). 1.1.11 Turan Graph ´ A k-partite graph is complete if any two vertices in different parts are adjacent. A simple complete k-partite graph on n vertices whose parts are of equal or almost equal sizes (that is, n/k or n/k ) is called a Tur´an graph and denoted Tk,n. a) Show that Tk,n has more edges than any other simple complete k-partite graph on n vertices. b) Determine e(Tk,n). 1.1.12 a) Show that if G is simple and m > n−1 2 , then G is connected. b) For n > 1, find a disconnected simple graph G with m = n−1 2 . 1.1.13 a) Show that if G is simple and δ > 1 2 (n − 2), then G is connected. b) For n even, find a disconnected 1 2 (n − 2)-regular simple graph. 1.1.14 For a simple graph G, show that the diagonal entries of both A2 and MMt (where Mt denotes the transpose of M) are the degrees of the vertices of G. 1.1.15 Show that the rank over GF(2) of the incidence matrix of a graph G is at most n − 1, with equality if and only if G is connected. 1.1.16 Degree Sequence If G has vertices v1,v2,...,vn, the sequence (d(v1),d(v2),...,d(vn)) is called a degree sequence of G. Let d := (d1,d2,...,dn) be a nonincreasing sequence of nonnegative integers, that is, d1 ≥ d2 ≥···≥ dn ≥ 0. Show that: a) there is a graph with degree sequence d if and only if n i=1 di is even, b) there is a loopless graph with degree sequence d if and only if n i=1 di is even and d1 ≤ n i=2 di. 1.1.17 Complement of a Graph Let G be a simple graph. The complement G of G is the simple graph whose vertex set is V and whose edges are the pairs of nonadjacent vertices of G. a) Express the degree sequence of G in terms of the degree sequence of G. b) Show that if G is disconnected, then G is connected. Is the converse true? ————— —————
1.1 Graphs and Their Representation111.1.18 GRAPHIC SEQUENCEA sequence d - (di,d2,..,dn) is graphic if there is a simple graph with degreesequence d. Show that:a) the sequences (7,6,5,4,3,3,2) and (6,6,5,4,3,3, 1) are not graphic,b) if d = (di, d2...,dn) is graphic and di ≥ d ≥ ... ≥ dn, then Dr- d, is evenngd,≤k(k-1) +min[k,d),1≤k≤n三i=k+(Erdos and Gallai (1960) showed that these necessary conditions for a sequencetobegraphicarealsosufficient.)1.1.19 Let d = (di,d2,...,dn) beofgers. Set d' := (d2 - 1,d3 - 1,.., ddi+1 --1, ddi+2.--*, dn).a) Show that d is graphic if and only if d' is graphicb)Using (a),describe an algorithm which accepts as input a nonincreasing sequence d of nonnegative integers, and returns either a simple graph with degreesequence d, if such a graph exists, or else a proof that d is not graphic.(V. HAVEL AND S.L. HAKIMI)1.1.20 Let S be a set of n points in the plane, the distance between any twoof which is at least one. Show that there are at most 3n pairs of points of S atdistance exactly one.1.1.21 EIGENVALUES OF A GRAPHRecall that the eigenvalues of a square matrix A are the roots of its characteristicpolynomial det(A- rI). An eigenvalue of a graph is an eigenvalue of its adjacencymatrix. Likewise, the characteristic polynomial of a graph is the characteristicpolynomial of its adjacency matrix. Show that:a) every eigenvalue of a graph is real,b) every rational eigenvalue of a graph is integral.1.1.22a) Let G be a k-regular graph. Show that:i) MM = A + I, where I is the n × n identity matrixi) k is an eigenvalue of G, with corresponding eigenvector1, the nn-vectorirwhich each entry is 1b) Let G be a complete graph of order n. Denote by J the n x n matrix all ofwhose entries are 1. Show thatA=J-Iii) det (J - (1 + )I) = (1 +>- n)(1 + )n-1c) Derive from (b) the eigenvalues of a complete graph and their multiplicities.anddeterminethecorrespondingeigenspaces
1.1 Graphs and Their Representation 11 1.1.18 Graphic Sequence A sequence d = (d1,d2,...,dn) is graphic if there is a simple graph with degree sequence d. Show that: a) the sequences (7, 6, 5, 4, 3, 3, 2) and (6, 6, 5, 4, 3, 3, 1) are not graphic, b) if d = (d1,d2,...,dn) is graphic and d1 ≥ d2 ≥···≥ dn, then n i=1 di is even and k i=1 di ≤ k(k − 1) + n i=k+1 min{k,di}, 1 ≤ k ≤ n (Erd˝os and Gallai (1960) showed that these necessary conditions for a sequence to be graphic are also sufficient.) 1.1.19 Let d = (d1,d2,...,dn) be a nonincreasing sequence of nonnegative integers. Set d := (d2 − 1,d3 − 1,...,dd1+1 − 1,dd1+2,...,dn). a) Show that d is graphic if and only if d is graphic. b) Using (a), describe an algorithm which accepts as input a nonincreasing sequence d of nonnegative integers, and returns either a simple graph with degree sequence d, if such a graph exists, or else a proof that d is not graphic. (V. Havel and S.L. Hakimi) 1.1.20 Let S be a set of n points in the plane, the distance between any two of which is at least one. Show that there are at most 3n pairs of points of S at distance exactly one. 1.1.21 Eigenvalues of a Graph Recall that the eigenvalues of a square matrix A are the roots of its characteristic polynomial det(A−xI). An eigenvalue of a graph is an eigenvalue of its adjacency matrix. Likewise, the characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix. Show that: a) every eigenvalue of a graph is real, b) every rational eigenvalue of a graph is integral. 1.1.22 a) Let G be a k-regular graph. Show that: i) MMt = A + kI, where I is the n × n identity matrix, ii) k is an eigenvalue of G, with corresponding eigenvector 1, the n-vector in which each entry is 1. b) Let G be a complete graph of order n. Denote by J the n × n matrix all of whose entries are 1. Show that: i) A = J − I, ii) det (J − (1 + λ)I) = (1 + λ − n)(1 + λ)n−1. c) Derive from (b) the eigenvalues of a complete graph and their multiplicities, and determine the corresponding eigenspaces.
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 orthogonal.) 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
1.2Isomorphismsand Automorphisms13GHHFig. 1.6. Isomorphic graphsInordertoshowthattwograstindicateasarophism between them. The pair of mappings (,) defined by(abcd)6123e4e5e6A:-Φ:=(f3f4f1fefsf2023is an isomorphism between the graphs G and H in Figure 1.6.In the case of simple graphs, the definition of isomorphism can be stated moreconcisely,becauseif (,)is an isomorphism between simplegraphs G and H,themapping is completely determined by ; indeed, (e) = e(u)e(u) for any edgee = uu of G. Thus one may define an isomorphism between two simple graphs Gand H as a bijection : V(G) - V(H) which preserves adjacency (that is, thevertices u and u are adjacent in G if and only if their images e(u) and d(u) areadjacent in H).Consider, for example, the graphs G and H in Figure 1.7.HFig. 1.7. Isomorphic simple graphsThe mapping(123456)9:-(bdfcea)is an isomorphism between G and H, as is
1.2 Isomorphisms and Automorphisms 13 a b d c e1 e2 e3 e4 e5 e6 G x x y z y w z w f1 f1 f2 f2 f3 f3 f4 f4 f5 f5 f6 f6 H H Fig. 1.6. Isomorphic graphs In order to show that two graphs are isomorphic, one must indicate an isomorphism between them. The pair of mappings (θ,φ) defined by θ := abcd wzyx φ := e1 e2 e3 e4 e5 e6 f3 f4 f1 f6 f5 f2 is an isomorphism between the graphs G and H in Figure 1.6. In the case of simple graphs, the definition of isomorphism can be stated more concisely, because if (θ,φ) is an isomorphism between simple graphs G and H, the mapping φ is completely determined by θ; indeed, φ(e) = θ(u)θ(v) for any edge e = uv of G. Thus one may define an isomorphism between two simple graphs G and H as a bijection θ : V (G) → V (H) which preserves adjacency (that is, the vertices u and v are adjacent in G if and only if their images θ(u) and θ(v) are adjacent in H). Consider, for example, the graphs G and H in Figure 1.7. 1 23 45 6 a b c e d f G H Fig. 1.7. Isomorphic simple graphs The mapping θ := 123456 bdfcea is an isomorphism between G and H, as is