a. Draw a graph that has 00012 00011 00021 11200 21100 as its adjacency matrix. Is this

Chapter 10, Problem 22

(choose chapter or problem)

a. Draw a graph that has

\(\left[\begin{array}{lllll} 0 & 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 2 & 1 \\ 1 & 1 & 2 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 \end{array}\right]\)

as its adjacency matrix. Is this graph bipartite? (For a definition of bipartite, see exercise 37 in Section 10.1.)

Definition: Given an \(m \times n\) matrix A whose ij th entry is denoted \(a_{i j}\), the transpose of A is the matrix \(\mathbf{A}^{t}\) whose ij th entry is \(a_{j i}\), for all \(i=1,2, \ldots, m\) and \(j=1,2, \ldots, n\).

Note that the first row of A becomes the first column of \(\mathbf{A}^{t}\), the second row of A becomes the second column of \(\mathbf{A}^{t}\), and so forth. For instance,

if \(\mathbf{A}=\left[\begin{array}{lll}0 & 2 & 1 \\ 1 & 2 & 3\end{array}\right]\), then \(\mathbf{A}^{t}=\left[\begin{array}{ll}0 & 1 \\ 2 & 2 \\ 1 & 3\end{array}\right]\).

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

\(\left[\begin{array}{ll} \mathbf{O} & \mathbf{A} \\ \mathbf{A}^{t} & \mathbf{O} \end{array}\right]\)

where A is a \(k \times(n-k)\) matrix for some integer k such that 0 < k < n, the top left O represents a \(k \times k\) matrix all of whose entries are \(0, \mathbf{A}^{t}\) is the transpose of A, and the bottom right O represents an \((n-k) \times(n-k)\) matrix all of whose entries are 0 .

Text Transcription:

[00012 00011 00021 11200 21100 ]

m time n

a_ij

a^t

a_ji

i=1,e2 dots m

j=1,2 dots n

A = [ 021 123]

At =[ 0 1 2 2 1 3 ]

[ O A At O ]

k times (n-k)

k times k

(n-k) times (n-k)