1 GraphsPROOF TECHNIQUE: COUNTING IN TWO WAYSIn proving Theorem 1.1, we used a common proof technique in combinatoricsnas countingintwoways.It consists of considering a suitablematrixand computing the sum of its entries in two different ways: firstly as the sumofitsrowsumsandseondlyasthsumfisclumnsums.Equatingthetwo quantities results in an identity. In the case of Theorem 1.1, the matrixwe considered was the incidence matrix of G. In order to prove the identity ofExercise 1.1.9a, the appropriate matrix to consider is the bipartite adjacencymatrix of the bipartite graph G[x,Y]. In both these cases, the choice of theappropriate matrix is fairly obvious. However, in some cases, making the rightchoice requires ingenuity.Note thatound on the sum of the column sums of a matrix isan upperclearly alson upper bound on the sum of its row sums (and wrice versaThemethodof counting imtwo ways may therefore be adaptedtoestablishinequalities. The proof of the following proposition llustrates this idea.Proposition 1.3 Let G[X,] be a bipartite graph without isolated verticessuch that d(r) ≥d(y) for all ryeE, wherereX and y eY. Then|X|<[Y],with equality if and only if d(r) = d(y) for all ry E E.Prossertion follows if we can find aofheamatrix with[X|rows andJY/ colunwhicheach rowssum isoneand each colusum is at mostone.Such a matrix can be obtained from the bipartite adjacency matrixBof G[X,] by dividing the row corresponding to vertex by d(), for each e X. (This is possible since d() + 0.) Because the sum of the entries of Bponding to is d(r), all row sums of the resulting matrix Bintherowcorreare equal to one. On the other hand, the sum of the entries in the column ofBcOonding to vertex y is 1/d(r), the sum being taken over all edgesry incident to y, and this sunost one because 1/d() ≤1/d(y) foreach edgey, by hypothesis, and because thereare d(y)edges incident toy.The above argument may be expressed more concisely as follows.>11[X]=Z=[Yd(y)d(a)aE-EdOeeEvEY EEEFurthermnore, if [X| - [Y], the middle inequality 1equality,implSDEing that d(r) = d(y) for all ry e E.An application of this proof technique to a problem in set theory about geometric configurations is described in Exercise 1.3.158 1 Graphs Proof Technique: Counting in Two Ways In proving Theorem 1.1, we used a common proof technique in combinatorics, known as counting in two ways. It consists of considering a suitable matrix and computing the sum of its entries in two different ways: firstly as the sum of its row sums, and secondly as the sum of its column sums. Equating these two quantities results in an identity. In the case of Theorem 1.1, the matrix we considered was the incidence matrix of G. In order to prove the identity of Exercise 1.1.9a, the appropriate matrix to consider is the bipartite adjacency matrix of the bipartite graph G[X,Y ]. In both these cases, the choice of the appropriate matrix is fairly obvious. However, in some cases, making the right choice requires ingenuity. Note that an upper bound on the sum of the column sums of a matrix is clearly also an upper bound on the sum of its row sums (and vice versa). The method of counting in two ways may therefore be adapted to establish inequalities. The proof of the following proposition illustrates this idea. Proposition 1.3 Let G[X,Y ] be a bipartite graph without isolated vertices such that d(x) ≥ d(y) for all xy ∈ E, where x ∈ X and y ∈ Y . Then |X|≤|Y |, with equality if and only if d(x) = d(y) for all xy ∈ E. Proof The first assertion follows if we can find a matrix with |X| rows and |Y | columns in which each row sum is one and each column sum is at most one. Such a matrix can be obtained from the bipartite adjacency matrix B of G[X,Y ] by dividing the row corresponding to vertex x by d(x), for each x ∈ X. (This is possible since d(x) = 0.) Because the sum of the entries of B in the row corresponding to x is d(x), all row sums of the resulting matrix B are equal to one. On the other hand, the sum of the entries in the column of B corresponding to vertex y is
1/d(x), the sum being taken over all edges xy incident to y, and this sum is at most one because 1/d(x) ≤ 1/d(y) for each edge xy, by hypothesis, and because there are d(y) edges incident to y. The above argument may be expressed more concisely as follows. |X| = x∈X y∈Y xy∈E 1 d(x) = x∈X y∈Y xy∈E 1 d(x) ≤ x∈X y∈Y xy∈E 1 d(y) = y∈Y x∈X xy∈E 1 d(y) = |Y | Furthermore, if |X| = |Y |, the middle inequality must be an equality, imply￾ing that d(x) = d(y) for all xy ∈ E.
An application of this proof technique to a problem in set theory about geo￾metric configurations is described in Exercise 1.3.15.