 13.1.1: Draw all trees of order 6.
 13.1.2: What is the smallest size of a graph G of order 5 such that G conta...
 13.1.3: Figure 13.5 shows four spanning trees of a connected graph G. There...
 13.1.4: Show that K6 contains three spanning trees T1, T2 and T3 such that ...
 13.1.5: Give an example of two nonisomorphic trees of the same order whose...
 13.1.6: (a) By Theorem 13.5, the minimum number of leaves in a tree of orde...
 13.1.7: How many trees are there whose complement is also a tree?
 13.1.8: Show that if v is a leaf in a nontrivial tree T , then T v is also ...
 13.1.9: If G is a graph of order n and size m with m = n 1, is G a tree?
 13.1.10: A tree T has 22 leaves, four vertices of degree 4 and three vertice...
 13.1.11: Show that if G is a connected graph of order n and size m = n, then...
 13.1.12: (a) Give an example of a graph G that is not a tree such that for e...
 13.1.13: A tree T has four vertices of degree 2, three vertices of degree 3,...
 13.1.14: A tree T of order 100 has only vertices of degrees 1 and 3. How man...
 13.1.15: A tree T has 7k endvertices, 2k 2 vertices of degree 3 and 2k + 2 ...
 13.1.16: A tree T has three vertices of degree 4 and five vertices of degree...
 13.1.17: Show that no tree of order 100 can have only vertices of degrees 1 ...
 13.1.18: What is the minimum order of a tree that contains at least one vert...
 13.1.19: (a) Use Theorem 13.12 to show that if T is a tree with maximum degr...
 13.1.20: What is the smallest positive integer k such that if F1 and F2 are ...
 13.1.21: Let G be a nontrivial connected graph of order n. Prove that G cont...
 13.1.22: Let T be a nontrivial tree of order n and let S be a set of vertice...
 13.1.23: Let T be a tree of order at least 3 and let G be a graph with V (G)...
Solutions for Chapter 13.1: Fundamental Properties of Trees
Full solutions for Discrete Mathematics  1st Edition
ISBN: 9781577667308
Solutions for Chapter 13.1: Fundamental Properties of Trees
Get Full SolutionsSince 23 problems in chapter 13.1: Fundamental Properties of Trees have been answered, more than 13911 students have viewed full stepbystep solutions from this chapter. 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 13.1: Fundamental Properties of Trees includes 23 full stepbystep solutions. This textbook survival guide was created for the textbook: Discrete Mathematics, edition: 1.

Block matrix.
A matrix can be partitioned into matrix blocks, by cuts between rows and/or between columns. Block multiplication ofAB is allowed if the block shapes permit.

CayleyHamilton Theorem.
peA) = det(A  AI) has peA) = zero matrix.

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

Eigenvalue A and eigenvector x.
Ax = AX with x#O so det(A  AI) = o.

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.

Four Fundamental Subspaces C (A), N (A), C (AT), N (AT).
Use AT for complex A.

Fourier matrix F.
Entries Fjk = e21Cijk/n give orthogonal columns FT F = nI. Then y = Fe is the (inverse) Discrete Fourier Transform Y j = L cke21Cijk/n.

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.

GramSchmidt orthogonalization A = QR.
Independent columns in A, orthonormal columns in Q. Each column q j of Q is a combination of the first j columns of A (and conversely, so R is upper triangular). Convention: diag(R) > o.

Graph G.
Set of n nodes connected pairwise by m edges. A complete graph has all n(n  1)/2 edges between nodes. A tree has only n  1 edges and no closed loops.

Hessenberg matrix H.
Triangular matrix with one extra nonzero adjacent diagonal.

Jordan form 1 = M 1 AM.
If A has s independent eigenvectors, its "generalized" eigenvector matrix M gives 1 = diag(lt, ... , 1s). The block his Akh +Nk where Nk has 1 's on diagonall. Each block has one eigenvalue Ak and one eigenvector.

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.

Multiplier eij.
The pivot row j is multiplied by eij and subtracted from row i to eliminate the i, j entry: eij = (entry to eliminate) / (jth pivot).

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

Row space C (AT) = all combinations of rows of A.
Column vectors by convention.

Schur complement S, D  C A } B.
Appears in block elimination on [~ g ].

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

Unitary matrix UH = U T = UI.
Orthonormal columns (complex analog of Q).

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