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.anddeterminethecorrespondingeigenspaces1.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 inte￾gers. 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 se￾quence 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.