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? ————— —————