 14.1.1: Show that each of the graphs in Figure 14.13 is planar by drawing i...
 14.1.2: . Determine the boundaries of the regions of the plane graph G in F...
 14.1.3: Let G be a planar graph and let G1 and G2 be two plane graphs obtai...
 14.1.4: Let G be a connected 3regular plane graph of order 8. How many reg...
 14.1.5: Let G be a connected plane graph of order 8 having five regions. Ho...
 14.1.6: The degrees of the vertices of a certain graph G are 3, 4, 4, 4, 5,...
 14.1.7: The degrees of the vertices of a certain graph G are 2, 2, 2, 3, 5,...
 14.1.8: A graph G of order n 3 has size m = 3n 6. Indicate which of the fol...
 14.1.9: A planar graph G of order n 3 has size m < 3n6. Let u and v be two ...
 14.1.10: (a) Give an example of a planar graph where no vertex of G has degr...
 14.1.11: A graph G has a vertex of degree 4 and all other vertices of G have...
 14.1.12: A certain graph G of order 6 has the following properties: (a) The ...
 14.1.13: State and solve the Five Houses and Two Utilities Problem.
 14.1.14: Determine all complete graphs Kn that are planar.
 14.1.15: Determine all complete bipartite graphs Ks,t that are planar, where...
 14.1.16: A graph G is a subdivision of a graph G having order n and size m. ...
 14.1.17: Let U be a subset of the vertex set of a graph G and suppose that H...
 14.1.18: Show that the Petersen graph (see Figure 14.15) is nonplanar by Kur...
 14.1.19: Determine, with explanation, which graphs in Figure 14.16 are planar.
 14.1.20: (a) Prove that if G is a planar graph of order n 3 and size m witho...
 14.1.21: Let G be a plane graph of order n 5 and size m. (a) Prove that if t...
 14.1.22: Determine all integers n 3 such that Cn is planar.
Solutions for Chapter 14.1: Planar Graphs
Full solutions for Discrete Mathematics  1st Edition
ISBN: 9781577667308
Solutions for Chapter 14.1: Planar Graphs
Get Full SolutionsThis textbook survival guide was created for the textbook: Discrete Mathematics, edition: 1. This expansive textbook survival guide covers the following chapters and their solutions. Discrete Mathematics was written by and is associated to the ISBN: 9781577667308. Chapter 14.1: Planar Graphs includes 22 full stepbystep solutions. Since 22 problems in chapter 14.1: Planar Graphs have been answered, more than 10380 students have viewed full stepbystep solutions from this chapter.

Basis for V.
Independent vectors VI, ... , v d whose linear combinations give each vector in V as v = CIVI + ... + CdVd. V has many bases, each basis gives unique c's. A vector space has many bases!

Big formula for n by n determinants.
Det(A) is a sum of n! terms. For each term: Multiply one entry from each row and column of A: rows in order 1, ... , nand column order given by a permutation P. Each of the n! P 's has a + or  sign.

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.)

Commuting matrices AB = BA.
If diagonalizable, they share n eigenvectors.

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

Cross product u xv in R3:
Vector perpendicular to u and v, length Ilullllvlll sin el = area of parallelogram, u x v = "determinant" of [i j k; UI U2 U3; VI V2 V3].

Diagonalizable matrix A.
Must have n independent eigenvectors (in the columns of S; automatic with n different eigenvalues). Then SI AS = A = eigenvalue matrix.

Elimination matrix = Elementary matrix Eij.
The identity matrix with an extra eij in the i, j entry (i # j). Then Eij A subtracts eij times row j of A from row i.

Exponential eAt = I + At + (At)2 12! + ...
has derivative AeAt; eAt u(O) solves u' = Au.

Factorization
A = L U. If elimination takes A to U without row exchanges, then the lower triangular L with multipliers eij (and eii = 1) brings U back to A.

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.

GaussJordan method.
Invert A by row operations on [A I] to reach [I AI].

Independent vectors VI, .. " vk.
No combination cl VI + ... + qVk = zero vector unless all ci = O. If the v's are the columns of A, the only solution to Ax = 0 is x = o.

Pivot.
The diagonal entry (first nonzero) at the time when a row is used in elimination.

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

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.

Standard basis for Rn.
Columns of n by n identity matrix (written i ,j ,k in R3).

Subspace S of V.
Any vector space inside V, including V and Z = {zero vector only}.

Sum V + W of subs paces.
Space of all (v in V) + (w in W). Direct sum: V n W = to}.