a. Draw a graph that has as its adjacency matrix. Is this

Chapter 10, Problem 22E

(choose chapter or problem)

a. Draw a graph that has as its adjacency matrix. Is this graph bipartite? (For a definition of bipartite, see exercise 37 in Section 10.1.)Note that the first row of A becomes the first column of At , the second row of A becomes the second column of At , and so forth. For instance, b. Show that a graph with n vertices is bipartite if, and only if, for some labeling of its vertices, its adjacency matrix has the form where A is a k × (n ? k) matrix for some integer k such that 0 < k < n, the top left O represents a k × k matrix all of whose entries are 0, At is the transpose of A, and the bottom right O represents an (n ? k) × (n ? k) matrix all of whose entries are 0.