Solved: A graph having n vertices such that every vertex is connected to every other

Chapter 10, Problem T1

(choose chapter or problem)

A graph having n vertices such that every vertex is connected to every other vertex has a vertex matrix given by Mn = 01111 1 10111 1 11011 1 11101 1 11110 1 . . . . . . . . . . . . . . . ... . . . 11111 0 In this problem we develop a formula for Mk n whose (i, j )-th entry equals the number of k-step connections from Pi to Pj . (a) Use a computer to compute the eight matrices Mk n for n = 2, 3 and for k = 2, 3, 4, 5. (b) Use the results in part (a) and symmetry arguments to show that Mk n can be written as Mk n = 01111 1 10111 1 11011 1 11101 1 11110 1 . . . . . . . . . . . . . . . ... . . . 11111 0 k = k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k . . . . . . . . . . . . . . . ... . . . k k k k k k (c) Using the fact that Mk n = MnMk1 n , show that k k = 0 n 1 1 n 2 k1 k1 with 1 1 = 0 1 (d) Using part (c), show that k k = 0 n 1 1 n 2 k1 0 1 (e) Use the methods of Section 5.2 to compute 0 n 1 1 n 2 k1 and thereby obtain expressions for k and k , and eventually show that Mk n = (n 1)k (1)k n ! Un + (1) k In where Un is the n n matrix all of whose entries are ones and In is the n n identity matrix. (f ) Show that for n > 2, all vertices for these directed graphs belong to cliques.