 10.7.1E: Can five houses be connected to two utilities without connections c...
 10.7.4E: In Exercises 2–4 draw the given planar graph without any crossings.
 10.7.2E: In Exercises 2–4 draw the given planar graph without any crossings.
 10.7.5E: In Exercise 59 determine whether the given graph is plannar. If so...
 10.7.3E: In Exercises 2–4 draw the given planar graph without any crossings.
 10.7.6E: In Exercise 59 determine whether the given graph is plannar. If so...
 10.7.8E: In Exercise 59 determine whether the given graph is plannar. If so...
 10.7.7E: In Exercise 59 determine whether the given graph is plannar. If so...
 10.7.9E: In Exercise 59 determine whether the given graph is plannar. If so...
 10.7.10E: Complete the argument in Example 3.
 10.7.14E: Suppose that a connected planar graph has 30 edges. If a planar rep...
 10.7.11E: Show that K5 is nonplanar using an argument similar to that given i...
 10.7.13E: Suppose that a connected planar graph has six vertices, each of deg...
 10.7.12E: Sup pose that a connected planar graph has eight vertices, each of ...
 10.7.17E: Suppose that a connected planar simple graph with e edges and v ver...
 10.7.16E: Suppose that a connected bipartite planar simple graph has e edges ...
 10.7.15E: Prove Corollary 3.
 10.7.19E: Which of these nonplanar graphs have the property that the removal ...
 10.7.18E: Suppose that a planar graph has k connected components, e edges, an...
 10.7.20E: In Exercises 20–22 determine whether the given graph is homeomorphi...
 10.7.24E: In Exercises 2325 use Kuratowski’s theorem to determine whether th...
 10.7.21E: In Exercises 20–22 determine whether the given graph is homeomorphi...
 10.7.22E: In Exercises 20–22 determine whether the given graph is homeomorphi...
 10.7.23E: In Exercises 2325 use Kuratowski’s theorem to determine whether th...
 10.7.25E: In Exercises 2325 use Kuratowski’s theorem to determine whether th...
 10.7.26E: The crossing number of a simple graph is the minimum number of cros...
 10.7.27E: The crossing number of a simple graph is the minimum number of cros...
 10.7.28E: The crossing number of a simple graph is the minimum number of cros...
 10.7.30E: Show that K3,3 has 2 as its thickness.
 10.7.29E: Show that if m and n are even positive integers, the crossing numbe...
 10.7.31E: Find the thickness of the graphs in Exercise 27.
 10.7.35E: Use Exercise 34 to show that the thickness of Km,n where m and n ar...
 10.7.32E: Show that if G is a connected simple graph with v vertices and e ed...
 10.7.34E: Show that if G is a connected simple graph with v vertices and e ed...
 10.7.33E: Use Exercise 32 to show that the thickness of Kn is at least whenev...
 10.7.37E: Draw K3,3 on the surface of a torus so that no edges cross.
 10.7.36E: Draw K5 on the surface of a torus (a doughnutshaped solid) so that...
Solutions for Chapter 10.7: Discrete Mathematics and Its Applications 7th Edition
Full solutions for Discrete Mathematics and Its Applications  7th Edition
ISBN: 9780073383095
Solutions for Chapter 10.7
Get Full SolutionsThis textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. Since 37 problems in chapter 10.7 have been answered, more than 200150 students have viewed full stepbystep solutions from this chapter. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095. Chapter 10.7 includes 37 full stepbystep solutions. This expansive textbook survival guide covers the following chapters and their solutions.

Affine transformation
Tv = Av + Vo = linear transformation plus shift.

Augmented matrix [A b].
Ax = b is solvable when b is in the column space of A; then [A b] has the same rank as A. Elimination on [A b] keeps equations correct.

Change of basis matrix M.
The old basis vectors v j are combinations L mij Wi of the new basis vectors. The coordinates of CI VI + ... + cnvn = dl wI + ... + dn Wn are related by d = M c. (For n = 2 set VI = mll WI +m21 W2, V2 = m12WI +m22w2.)

Characteristic equation det(A  AI) = O.
The n roots are the eigenvalues of A.

Cholesky factorization
A = CTC = (L.J]))(L.J]))T for positive definite A.

Cofactor Cij.
Remove row i and column j; multiply the determinant by (I)i + j •

Complex conjugate
z = a  ib for any complex number z = a + ib. Then zz = Iz12.

Cramer's Rule for Ax = b.
B j has b replacing column j of A; x j = det B j I det A

Dimension of vector space
dim(V) = number of vectors in any basis for V.

Fast Fourier Transform (FFT).
A factorization of the Fourier matrix Fn into e = log2 n matrices Si times a permutation. Each Si needs only nl2 multiplications, so Fnx and Fn1c can be computed with ne/2 multiplications. Revolutionary.

Full row rank r = m.
Independent rows, at least one solution to Ax = b, column space is all of Rm. Full rank means full column rank or full row rank.

Linearly dependent VI, ... , Vn.
A combination other than all Ci = 0 gives L Ci Vi = O.

Lucas numbers
Ln = 2,J, 3, 4, ... satisfy Ln = L n l +Ln 2 = A1 +A~, with AI, A2 = (1 ± /5)/2 from the Fibonacci matrix U~]' Compare Lo = 2 with Fo = O.

Polar decomposition A = Q H.
Orthogonal Q times positive (semi)definite H.

Rayleigh quotient q (x) = X T Ax I x T x for symmetric A: Amin < q (x) < Amax.
Those extremes are reached at the eigenvectors x for Amin(A) and Amax(A).

Reduced row echelon form R = rref(A).
Pivots = 1; zeros above and below pivots; the r nonzero rows of R give a basis for the row space of A.

Rotation matrix
R = [~ CS ] rotates the plane by () and R 1 = RT rotates back by (). Eigenvalues are eiO and eiO , eigenvectors are (1, ±i). c, s = cos (), sin ().

Row picture of Ax = b.
Each equation gives a plane in Rn; the planes intersect at x.

Semidefinite matrix A.
(Positive) semidefinite: all x T Ax > 0, all A > 0; A = any RT R.

Volume of box.
The rows (or the columns) of A generate a box with volume I det(A) I.