We now observe that since-1 and 01,the mean squre density also lies between 0 and 1 Lemma 1 For every partition of the verter set of a graph G,the mean square density lies between O and 1. Another important property of mean square density is that it cnot increase under refinement of a partition.That is,we have the following. Lemma 2 Let G be a gruph with verter set V(G).f is a partition f V(G)and Y1,Y2,...,Y is a refinement of x1,X2.....X then the mean square density of Y,Y2,....Ye is at least the mean square density of X1,X2,...,Xk. Proof Because the Y partition is a refinement of,everyXi may be rewritten as a disjoint union Xi U...U Xia;where each Xi Yi,for some j.Now,by the Cauchy-Schwarz inequality, d(X,X)2= x） 2 ≤ 空)（医） ∑KxH） = ∑xlxd(X,Xn} xalxl Therefore X1dX,x}P≤∑Xxacx.,Xr. n2 s.t n2 Adding over all values of i and j implies the lemma. An analogous result also holds for bipartite graphs G.That is,if G is a bipartite graph between two these partitions, ∑X1ax.ys∑2w1Z,w. n2 We will now show that if X and Y are two sets of vertices and the graph between them is not-regular then there is a partition of each of X and Y for which the mean square density increases. Lemma 3 Let G be a graph and suppose X and Y are subsets of the verter set V(G).If d(X,Y)=a and the graph between X and Y is not e-regular then there are partitions X=XUX2 and Y=YiUY2 such that ra4 2 We now observe that since P 1≤i,j≤k |Xi||Xj | n2 = 1 and 0 ≤ d(Xi , Xj ) ≤ 1, the mean square density also lies between 0 and 1. Lemma 1 For every partition of the vertex set of a graph G, the mean square density lies between 0 and 1. Another important property of mean square density is that it cannot increase under refinement of a partition. That is, we have the following. Lemma 2 Let G be a graph with vertex set V (G). If X1, X2, . . . , Xk is a partition of V (G) and Y1, Y2, . . . , Y` is a refinement of X1, X2, . . . , Xk, then the mean square density of Y1, Y2, . . . , Y` is at least the mean square density of X1, X2, . . . , Xk. Proof Because the Yi partition is a refinement of the Xi partition, every Xi may be rewritten as a disjoint union Xi1 ∪ · · · ∪ Xiai , where each Xiai = Yj , for some j. Now, by the Cauchy-Schwarz inequality, d(Xi , Xj ) 2 = X s,t |Xis||Xjt| |Xi ||Xj | d(Xis, Xyt) !2 ≤ X s,t |Xis||Xjt| |Xi ||Xj | ! X s,t |Xis||Xjt| |Xi ||Xj | d(Xis, Xyt) 2 ! = X s,t |Xis||Xjt| |Xi ||Xj | d(Xis, Xyt) 2 . Therefore, |Xi ||Xj | n2 d(Xi , Xj ) 2 ≤ X s,t |Xis||Xjt| n2 d(Xis, Xyt) 2 . Adding over all values of i and j implies the lemma. ✷ An analogous result also holds for bipartite graphs G. That is, if G is a bipartite graph between two sets X and Y , ∪iXi and ∪iYi are partitions of X and Y and ∪iZi and ∪iWi refine these partitions, then X i,j |Xi ||Yj | n2 d(Xi , Yj ) 2 ≤ X i,j |Zi ||Wj | n2 d(Zi , Wj ) 2 . We will now show that if X and Y are two sets of vertices and the graph between them is not-regular then there is a partition of each of X and Y for which the mean square density increases. Lemma 3 Let G be a graph and suppose X and Y are subsets of the vertex set V (G). If d(X, Y ) = α and the graph between X and Y is not -regular then there are partitions X = X1∪X2 and Y = Y1∪Y2 such that X 1≤i,j≤2 |Xi ||Yj | |X||Y | d(Xi , Yj ) 2 ≥ α 2 +  4 . 2